Dare2Solve
The recoverTree
function corrects a binary search tree (BST) where exactly two nodes have been swapped by mistake. The goal is to identify these two nodes and swap them back to restore the BST property, where the left subtree of any node contains only nodes with values less than the node’s value, and the right subtree only nodes with values greater.
The problem can be approached by performing an in-order traversal of the BST. In a correctly ordered BST, the values retrieved during an in-order traversal should appear in ascending order. When two nodes are swapped, this order will be violated in exactly two places. By identifying these two violations, we can determine which nodes need to be swapped back to correct the tree.
In-order Traversal:
prev
) visited.Identify Swapped Nodes:
prev
). If so, a violation of the BST property has been detected.big
and the current node as small
.small
node to the current node.Swap Values:
big
and small
) are swapped to restore the BST property.Edge Cases:
The time complexity is (O(n)), where n
is the number of nodes in the tree. This is because each node is visited exactly once during the in-order traversal.
The space complexity is (O(h)), where h
is the height of the tree. This space is used by the recursion stack during the in-order traversal. In the worst case, for a completely unbalanced tree, this could be (O(n)), while for a balanced tree, it would be (O(\log n)).
class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode *small = nullptr, *big = nullptr, *prev = nullptr;
std::function<void(TreeNode*)> inorder = [&](TreeNode* r) {
if (!r) return;
inorder(r->left);
if (prev && prev->val > r->val) {
small = r;
if (big) return;
big = prev;
}
prev = r;
inorder(r->right);
};
inorder(root);
std::swap(small->val, big->val);
}
};
class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
small = big = prev = None
def inorder(r):
nonlocal small, big, prev
if not r:
return
inorder(r.left)
if prev and prev.val > r.val:
small = r
if not big:
big = prev
prev = r
inorder(r.right)
inorder(root)
small.val, big.val = big.val, small.val
class Solution {
private TreeNode small = null, big = null, prev = null;
public void recoverTree(TreeNode root) {
inorder(root);
int temp = small.val;
small.val = big.val;
big.val = temp;
}
private void inorder(TreeNode r) {
if (r == null) return;
inorder(r.left);
if (prev != null && prev.val > r.val) {
small = r;
if (big != null) return;
big = prev;
}
prev = r;
inorder(r.right);
}
}
var recoverTree = function (root) {
let small = null, big = null, prev = null;
let inorder = function (r) {
if (r == null) return;
inorder(r.left);
if (prev && prev.val > r.val) {
small = r;
if (big) return;
big = prev;
}
prev = r;
inorder(r.right);
return;
}
inorder(root);
[small.val, big.val] = [big.val, small.val];
};