Recover Binary Search Tree — LC 99 In-Order Inversion Trick

Problem Statement#

You are given the root of a binary search tree where the values of exactly two nodes have been swapped by mistake. Recover the tree without changing its structure (only swap back their values).

Constraints:

• The number of nodes is in the range [2, 1000]
• -2^31 <= Node.val <= 2^31 - 1

Input:  root = [1,3,null,null,2]
Output: [3,1,null,null,2]
        Nodes 1 and 3 were swapped.

Input:  root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
        Nodes 2 and 3 were swapped.

Why This Problem Matters#

LeetCode 99 Recover Binary Search Tree is a Medium-to-Hard FAANG question asked at Amazon, Google, Meta, and Microsoft. It is the canonical test of two BST instincts: (1) in-order traversal of a valid BST yields a strictly ascending sequence, and (2) Morris traversal achieves O(1) extra space.

This problem rewards candidates who recognize that a swap creates either one inversion (when the swapped nodes are adjacent in in-order) or two inversions (when they are not). Identifying the FIRST node of the FIRST inversion and the SECOND node of the LAST inversion gives the swapped pair — a beautifully concise observation.

The Morris traversal follow-up makes this an ideal whiteboard challenge: O(n) time with O(1) auxiliary space by using right-pointer threading.

The Core Insight#

In a valid BST, in-order traversal visits values in strictly ascending order. After two values are swapped, the in-order sequence has either one or two inversions:

• Adjacent swap (nodes neighbor in in-order): exactly one inversion ... A B ... where A > B. Swap A and B.
• Non-adjacent swap: two inversions. The first node of the FIRST inversion and the second node of the LAST (second) inversion are the misplaced pair.

So during in-order traversal, track prev, first, and second:

• On detecting prev.val > node.val:
  • If first is null, set first = prev (record FIRST inversion's first element).
  • Always set second = node (overwrite to capture LAST inversion's second element).

After traversal, swap first.val and second.val.

Visual Dry Run#

Tree: [3,1,4,null,null,2] (in-order: 1, 3, 2, 4)

Swap first.val (3) and second.val (2). Tree becomes valid BST.

Solution (Optimal)#

class Solution:
    def recoverTree(self, root):
        self.first = self.second = self.prev = None
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            if self.prev and self.prev.val > node.val:
                if not self.first:
                    self.first = self.prev
                self.second = node
            self.prev = node
            inorder(node.right)
        inorder(root)
        self.first.val, self.second.val = self.second.val, self.first.val

var recoverTree = function(root) {
    let first = null, second = null, prev = null;
    const inorder = (node) => {
        if (!node) return;
        inorder(node.left);
        if (prev && prev.val > node.val) {
            if (!first) first = prev;
            second = node;
        }
        prev = node;
        inorder(node.right);
    };
    inorder(root);
    [first.val, second.val] = [second.val, first.val];
};

Time: O(n) — single in-order traversal. Space: O(h) recursion (or O(1) with Morris traversal).

Common Mistakes#

• Setting first = prev only on the FIRST inversion — correct; do not overwrite first on later inversions.
• Setting second = prev instead of second = node — wrong direction in the inversion.
• Resetting second only on first inversion — fails on adjacent-swap case where there is only one inversion.
• Allocating an array of in-order values — works but uses O(n) extra space, missing the optimal solution.
• Forgetting initial prev = null — crashes on the first node.

Interview Tips#

• Explain the in-order ordering invariant before coding.
• Distinguish adjacent vs non-adjacent swap by drawing a 4-node tree for each case.
• Mention Morris traversal as the O(1)-space follow-up.
• Confirm: "Swap values, not nodes" — preserves structure as required.

Follow-up Questions#

• O(1) space? Morris traversal: thread right pointers temporarily, restore on the way back.
• Three nodes swapped? Multiple inversions; track all involved values and reassign.
• Detect more general corruption? Re-validate full BST property and emit full diff.
• Functional / immutable version? Build a new tree during traversal — O(n) extra space.
• Streamed traversal (no recursion)? Iterative in-order with a stack.

Key Takeaways#

• LeetCode 99 is a Medium-difficulty FAANG BST question asked at Amazon, Google, and Meta.
• A valid BST's in-order traversal is strictly ascending; a 2-node swap creates 1 or 2 inversions.
• Track prev, first (set on FIRST inversion's first node), second (overwritten to LAST inversion's second node).
• Time complexity O(n); space O(h) for recursion or O(1) with Morris traversal.
• Swap node values rather than node pointers — required by the problem to preserve structure.
• Adjacent swaps yield 1 inversion; non-adjacent yield 2 — the algorithm handles both uniformly.
• Morris traversal with O(1) space is the elite follow-up that distinguishes top candidates.