#99
Recover Binary Search Tree
Medium Inorder to find swapped pair
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Exactly two nodes of a BST had their values swapped by mistake. Fix the tree without changing its structure.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: two values were swapped by mistake; fix them.
Why this works: inorder should be increasing. The swap creates one or two "drops"; the first wrong node is at the first drop, the second at the last drop.
Example: inorder 1, 3, 2, 4 (3 and 2 swapped)
drop at 3 > 2 → first 3, second 2swap back → 1, 2, 3, 4
✦Hints open one at a time
The inorder sequence should be increasing. Swapping two values creates one or two "drops" (prev > cur).
The first wrong node is prev at the first drop; the second is cur at the last drop.
↗Approach
Inorder traversal tracking prev. On each drop, set first (only once) to prev and second to cur. Swap their values at the end.
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
private TreeNode first, second, prev;
public void recoverTree(TreeNode root) {
inorder(root);
int t = first.val;
first.val = second.val;
second.val = t;
}
private void inorder(TreeNode n) {
if (n == null) return;
inorder(n.left);
if (prev != null && prev.val > n.val) { // a drop in the sorted order
if (first == null) first = prev;
second = n;
}
prev = n;
inorder(n.right);
}
}!Common mistake
Assuming there are always two drops — adjacent swapped nodes create only one.
Complexity
- Time: O(n).
- Space: O(h) (Morris traversal brings it to O(1)).
Topic: Binary Search Trees
🎬 Episodes 61–63: video coming soon