Recover Binary Search Tree

Recover Binary Search Tree takes a valid BST whose two nodes were accidentally swapped and asks you to put it right — without rebuilding the tree. The elegant solution rests on one fact: an in-order traversal of a BST is sorted.

The slow way first

The blunt approach: do an in-order traversal, copy all the values into a list, sort the list, then walk the tree in-order again writing the sorted values back. That works and is easy to reason about, but it costs O(n) extra space for the list and O(n log n) time for the sort. We can do better — and interviewers expect it.

The question to ask: if the tree were correct, what would the in-order walk look like? It would be strictly increasing. So every place where it is not increasing points straight at an offender.

The idea: catch the dips

Walk the tree in-order while remembering prev, the previously visited node. A correct BST never lets prev.val > node.val. When it does, we have a violation (a dip):

• The first dip we hit: the offender is prev (the larger value that landed too early). Save it as first.
• The last dip we hit: the offender is the current node (the smaller value). Save it as second.

If the two swapped nodes were adjacent in the in-order order there is only one dip; if they were far apart there are two. Either way first and second end up correct. Swap their values and you are done.

The key insight: we only ever set first once (on the very first dip) but we keep overwriting second on every dip, so it ends up holding the last offender.

Walk through it

Step through the animation. The cur pointer follows the in-order order: 1, then root 3, then 2, then 4. Between 3 and 2 we hit a dip (3 > 2), so first = 3 and second = 2. No other dip appears. At the end we swap those two values and the in-order order becomes 1, 2, 3, 4.

Pseudocode

first = second = prev = null
in-order traversal of the tree:
    at each node:
        if prev exists and prev.val > node.val:   # a dip
            if first is null: first = prev        # only the first time
            second = node                         # always the latest
        prev = node
swap first.val and second.val

The Python solution

def recover_tree(root):
    first = second = prev = None
    def inorder(node):
        nonlocal first, second, prev
        if node is None:
            return
        inorder(node.left)
        if prev and prev.val > node.val:
            if first is None:
                first = prev
            second = node
        prev = node
        inorder(node.right)
    inorder(root)
    first.val, second.val = second.val, first.val

• first, second, and prev are the only extra state — three references, O(1) space.
• inorder(node.left) first, then process node, then inorder(node.right) — that ordering is the in-order walk that yields sorted values.
• Line 8 is the heart: prev.val > node.val detects a dip in the otherwise-increasing sequence.
• if first is None: first = prev records the first offender once; second = node is reassigned on every dip, so it ends as the last offender.
• prev = node advances the running pointer before recursing right.
• The final line swaps just the two values — the tree structure (the links) is never touched.

Complexity

Time is O(n) — a single traversal. Space is O(h) for the recursion stack (the tree height); a Morris in-order traversal can push that down to true O(1), but O(h) is the expected answer.

When this pattern shows up

Practice