Recover Binary Search Tree
Problem Statement
You are given the root of a Binary Search Tree where exactly two nodes have been swapped by mistake. Recover the tree without changing its structure by swapping the two incorrect node values back.
Input
The root pointer of a BST whose shape is unchanged but whose two node values are in the wrong positions.
Output
The same tree root after the two incorrect values have been swapped back. The function modifies the tree in place.
Constraints
- •
2 <= number of nodes <= 1000 - •
-2^31 <= Node.val <= 2^31 - 1 - •
Exactly two nodes in the BST have been swapped - •
All node values are unique
Examples
Example 1
root = [1,3,null,null,2]
[3,1,null,null,2]Example 2
root = [3,1,4,null,null,2]
[2,1,4,null,null,3]Learning Objectives
- Use inorder traversal to expose the sorted sequence of a BST.
- Detect one or two inversion points caused by exactly two swapped values.
- Track **previous**, **first**, and **second** pointers during traversal.
- Explain why swapping values fixes the tree without changing pointers.
Intuition
Pattern Recognition
The technique is inorder violation detection. The signal is a BST whose structure is intact but two values are swapped. Since a correct BST has a strictly increasing inorder sequence, the swapped nodes appear exactly where that sequence drops.
If the swapped nodes are adjacent in inorder order, there is one drop, such as 1, 3, 2, 4. The first offender is the previous node 3, and the second offender is the current node 2. If the swapped nodes are far apart, there are two drops, such as 3, 2, 1. The first offender is still the previous node at the first drop, and the second offender is updated to the current node at the second drop.
Common mistakes
- ×Trying to rebuild the BST instead of preserving the original tree structure.
- ×Recording only the first inversion, which fails when the swapped nodes are not adjacent in inorder order.
- ×Comparing a node with its parent instead of with the previous node in inorder order.
- ×Swapping node references instead of swapping values, which can accidentally change the shape.
Algorithm Explanation
Key idea
Inorder traversal should produce a sorted sequence. Keep previous, the node visited immediately before the current node. Whenever previous.val > current.val, you found an inversion. On the first inversion, set first = previous. On every inversion, set second = current. After traversal, swap first.val and second.val.
Recursion walkthrough
Use [1,3,null,null,2]. The inorder visit order is 3, then 2, then 1. When visiting 2, the previous node is 3, so 3 > 2 is the first inversion. Set first = 3 and second = 2. When visiting 1, the previous node is 2, so 2 > 1 is another inversion. Keep first = 3 and update second = 1.
At the end, swapping values 3 and 1 restores the inorder sequence to 1, 2, 3 and the tree becomes a valid BST again. The Morris traversal follow-up can reduce extra space to O(1) by threading the tree temporarily, but the cleaner interview implementation uses the normal O(h) recursion stack.
Algorithm
- Initialise first, second, and previous as empty pointers.
- Traverse the tree inorder.
- Before moving past a node, compare previous.val with the current node value if previous exists.
- If previous.val > current.val and first is empty, set first = previous.
- For every inversion, set second = current.
- Update previous to the current node and continue inorder.
- Swap first.val and second.val after traversal.
Solutions
Solution: Inorder DFS with previous pointer
Use this by default. It is concise, preserves the tree shape, and clearly demonstrates how the sorted inorder invariant exposes the two swapped values.
Run inorder DFS and compare each node with the previously visited node. The first time order drops, the previous node is the first swapped node. The current node is a candidate for the second swapped node, and it must be updated again if a second drop appears.
Step-by-step
- Keep fields for first, second, and previous.
- Visit the left subtree.
- If previous exists and previous.val > node.val, record an inversion.
- On the first inversion, set first to previous.
- On every inversion, set second to the current node.
- Move previous to the current node and visit the right subtree.
- Swap the values stored in first and second.
O(n)
O(h)
Every node is visited once; recursion uses stack space equal to the tree height.
Java implementation
Dry Run
Sample input
root = [1,3,null,null,2]. The inorder stream should be increasing, but it appears as 3, 2, 1.
| visit order | current | previous | violation | first | second |
|---|---|---|---|---|---|
| 1 | 3 | none | no comparison | none | none |
| 2 | 2 | 3 | **3 > 2** | 3 | 2 |
| 3 | 1 | 2 | **2 > 1** | 3 | 1 |
After traversal, first = 3 and second = 1. Swapping those values changes the inorder order to 1, 2, 3.
Interview Tips
Use the phrase inorder should be sorted before coding. Then explain adjacent versus non-adjacent swaps: one inversion still sets both nodes, while two inversions keep the first previous offender and update the second current offender. Mention Morris traversal as a space follow-up, but code the recursive O(h) version unless specifically asked for constant space.
Likely follow-ups
- Can you recover the BST using Morris inorder traversal with **O(1)** extra space?
- How would you detect whether a BST is valid without modifying it?
- What if more than two nodes were out of order?
- How would duplicate values change the inversion comparison?
Similar Problems
Key Takeaways
- A valid BST has a strictly increasing inorder traversal.
- Exactly two swapped nodes create one or two inorder inversions.
- **first** is the previous node from the first inversion; **second** is the current node from the latest inversion.
- Swapping values restores the BST while preserving its structure.