Recover Binary Search Tree
You are given the root of a BST in which exactly two nodes have been swapped by mistake. Recover the tree without changing its structure.
Constraints:
- The number of nodes is in the range
[2, 1000]. -2^31 <= Node.val <= 2^31 - 1
Follow-up: can you do it with O(1) space?
Intuition
1 1 32 / /3 3 should 14 \ be \5 2 2A valid BST has a strictly increasing inorder traversal. When two nodes are swapped, the inorder sequence is mostly sorted, with one or two places where it dips (a value is bigger than the one after it).
- If the swapped nodes are not adjacent in inorder, there are two dips. The sequence
1 6 3 4 5 2 7has dips at6 > 3and5 > 2. The first wrong node is the bigger value of the first dip (6), and the second wrong node is the smaller value of the second dip (2). - If they are adjacent, there is only one dip, such as
1 2 4 3 5. The two wrong nodes are exactly that pair (4 and 3).
So one inorder traversal that remembers the previous node is enough to find them.
Approach: Inorder with a Previous Pointer
Keep four pointers: prev (the last node visited), first, middle and last.
- Do an inorder traversal. At each node, compare it with
prev. - If
prevexists andprev.val > node.val, we found a dip:- If it is the first dip, set
first = prevandmiddle = node. - Otherwise (the second dip), set
last = node.
- If it is the first dip, set
- Set
prev = nodeand continue. - After the traversal:
- If
lastis set (two dips), swap the values offirstandlast. - Otherwise (one dip), swap the values of
firstandmiddle.
- If
We swap values, not nodes, so the structure stays the same. A Morris inorder traversal gives the same logic in O(1) space, which answers the follow-up.
Code
class Solution {TreeNode *first = nullptr, *middle = nullptr, *last = nullptr, *prev = nullptr;void inorder(TreeNode* node) {if (node == nullptr) return;inorder(node->left);if (prev != nullptr && prev->val > node->val) {if (first == nullptr) {first = prev;middle = node;} else {last = node;}}prev = node;inorder(node->right);}public:void recoverTree(TreeNode* root) {first = middle = last = prev = nullptr;inorder(root);if (last != nullptr) swap(first->val, last->val);else swap(first->val, middle->val);}};
Complexity
One inorder traversal visits each node once.
Recursion stack depth equals the tree height. A Morris inorder traversal reduces this to O(1).