0
$\begingroup$

Given a binary search tree(can have any height) .Some nodes its value changed and violate bst property how we can recover binary search tree property in-place by just swapping a node with its children's.

I think it can be done in $O(n^2)$ because a bst has height at most $n$ and start from parent of leaves and if two nodes violate bst property we can swap it by parent,but i want give a formal prove,anyone have any suggestion?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy