On this page

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 3
2 / /
3 3 should 1
4 \ be \
5 2 2

A 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 7 has dips at 6 > 3 and 5 > 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.

  1. Do an inorder traversal. At each node, compare it with prev.
  2. If prev exists and prev.val > node.val, we found a dip:
    • If it is the first dip, set first = prev and middle = node.
    • Otherwise (the second dip), set last = node.
  3. Set prev = node and continue.
  4. After the traversal:
    • If last is set (two dips), swap the values of first and last.
    • Otherwise (one dip), swap the values of first and middle.

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

Time: O(n)

One inorder traversal visits each node once.

Space: O(h)

Recursion stack depth equals the tree height. A Morris inorder traversal reduces this to O(1).

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"The inorder traversal of a valid BST is strictly increasing, so two swapped nodes show up as dips where a value is greater than the next one. If the swapped nodes are not adjacent there are two dips, and the wrong nodes are the larger value of the first dip and the smaller value of the second dip. If they are adjacent there is one dip, and the wrong nodes are that pair. So I do one inorder traversal with a previous pointer, record first and middle at the first dip, and last at the second dip. At the end I swap the values of first and last if there were two dips, otherwise first and middle. Time is O of n and space is O of h, and a Morris traversal gets it to O of one."
Next TopicLargest Bst in Binary Tree