DSA problem
Recover Binary Search Tree
You are given the root of a binary search tree in which exactly two nodes have been swapped by mistake. Recover the tree without changing its structure — only the values of those two nodes may be modified.
Because an in-order traversal of a valid BST yields a strictly increasing sequence, the two swapped values show up as out-of-order pairs in the traversal. The trick is figuring out which two nodes to swap.
If the two swapped nodes are adjacent in the in-order sequence (e.g., [1, 3, 2, 4]), there is exactly one "dip" where prev.val > curr.val. The two culprits are prev and curr from that dip.
If the two swapped nodes are not adjacent in the in-order sequence (e.g., [1, 5, 3, 4, 2, 6] from swapping 5 and 2), there are exactly two dips. The first culprit is the prev of the first dip; the second culprit is the curr of the second dip.
Combining both cases: walk in-order while remembering the previous node. On the first violation record first = prev and second = curr. On any subsequent violation update second = curr (but keep first from the first dip). After the walk, swap the values of first and second. With Morris traversal you can do this in O(n) time and O(1) extra space; the cleaner iterative-stack version uses O(h) auxiliary space.
Examples
root = [1,3,null,null,2][3,1,null,null,2]root = [3,1,4,null,null,2][2,1,4,null,null,3]root = [4,2,6,1,5,3,7][4,2,6,1,3,5,7]Constraints
- The number of nodes in the tree is in the range [2, 1000].
- -2^31 <= Node.val <= 2^31 - 1
- Exactly two nodes in the tree have been swapped.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.