Recover Binary Search Tree

Recover Binary Search Tree

What is this problem about?

The Recover Binary Search Tree problem gives you a BST where exactly two nodes were accidentally swapped. Find those two nodes and swap them back to restore the BST. This medium coding problem uses Morris Traversal (O(1) space) or inorder DFS to find the two "out-of-order" nodes. The BST, DFS, binary tree, and tree interview pattern is demonstrated.

Why is this asked in interviews?

Apple, Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it tests in-order BST traversal with anomaly detection. The key insight: in a valid BST, inorder traversal is strictly increasing; the swapped nodes create at most two "drops" in the sequence.

Algorithmic pattern used

Inorder traversal + anomaly detection. Perform inorder traversal. Track the previous node. When prev.val > current.val (a drop), record: first anomaly node = prev (first drop), second anomaly node = current (last drop). After traversal, swap the values of the two anomaly nodes.

Example explanation

BST (inorder should be 1,2,3,4,5): nodes 1 and 3 swapped (now reads 3,2,1,4,5 inorder).

• Traverse: prev=3,curr=2: drop! first=3, second=2.
• prev=2,curr=1: drop! second=1 (update second only). Swap values of nodes 3 and 1. BST restored.

Common mistakes candidates make

• Not handling the two-drop case (adjacent swapped nodes have only one drop).
• Swapping only the first pair found (must update second on the second drop).
• Swapping node pointers instead of values.
• Not using Morris traversal for O(1) space (though DFS with O(h) space is acceptable).

Interview preparation tip

Recover BST demonstrates "inorder anomaly detection." The two swapped nodes create one or two violations in the sorted sequence. Always track both first and update second at each violation. The O(1) space solution using Morris traversal is impressive — worth mentioning even if not implementing. Practice "validate BST" and "find inorder successor/predecessor" as foundations.