Recover Binary Search Tree: Find and Fix Two Swapped Nodes

You are given the root of a binary search tree where exactly two nodes have been swapped by mistake. Recover the tree by swapping those two values back, without changing the tree's structure.

This is LeetCode 99: Recover Binary Search Tree. It builds directly on the property that inorder traversal of a valid BST produces sorted output. If two nodes are swapped, the inorder sequence will have violations of that sorted order, and those violations tell you exactly which two nodes need to be fixed.

Example: root = [1, 3, null, null, 2]. Nodes 3 and 1 are swapped. The recovered tree is [3, 1, null, null, 2].

The core insight

A valid BST has the property that its inorder traversal is strictly increasing. If you swap two nodes, the inorder sequence will no longer be sorted. The trick is figuring out which two nodes were swapped by looking at where the sorted order breaks.

Consider the corrupted tree above. Its inorder traversal produces [3, 2, 1, 4]. In a valid BST, the inorder should be [1, 2, 3, 4]. You can spot two places where the sequence decreases instead of increases:

• 3 > 2 (first violation)
• 2 > 1 (second violation)

The swapped nodes are always:

1. The larger node from the first violation (3 in this case)
2. The smaller node from the last violation (1 in this case)

Why does this work? When two non-adjacent values are swapped in a sorted sequence, the larger value ends up too early (causing the first drop) and the smaller value ends up too late (causing the second drop). The first violation's larger element is the one that does not belong where it is, and the last violation's smaller element is the other one.

The approach

1. Perform an inorder traversal of the BST.
2. Track the previously visited node (prev).
3. Whenever prev.val > current.val, you have found a violation.
4. On the first violation, record first = prev and second = current.
5. On any subsequent violation, update second = current.
6. After the traversal, swap first.val and second.val.

Python solution

def recover_tree(root):
    first = second = prev = None

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

    inorder(root)
    first.val, second.val = second.val, first.val

Walkthrough

Let's trace through the corrupted tree where nodes 3 and 1 are swapped. The tree structure is:

      1          (should be 3)
     / \
    3   4        (should be 1)
     \
      2

The inorder traversal visits nodes in left-root-right order: 3, 2, 1, 4.

The algorithm found two violations in the inorder sequence. From the first violation (3 > 2), it recorded first = 3. From the second violation (2 > 1), it updated second = 1. Swapping the values of those two nodes restores the BST.

Why we track first and second this way

There are two cases to consider for swapped nodes:

Case 1: Non-adjacent nodes in inorder. This is the example above. Two violations appear because the swapped values are far apart in the sorted order. The first violation identifies where the larger swapped value sits (too early), and the second violation identifies where the smaller swapped value sits (too late).

Case 2: Adjacent nodes in inorder. If the two swapped nodes are next to each other in the inorder sequence, there is only one violation. For example, if 2 and 3 are swapped in [1, 3, 2, 4], the only drop is 3 > 2. In this case, first = 3 and second = 2 are both set during that single violation. No second violation occurs, and first and second already point to the correct pair.

The algorithm handles both cases with the same code. On the first violation, it sets both first and second. If a second violation appears, it updates second. If no second violation appears, the original assignments are already correct.

Complexity analysis

Time is O(n) because the inorder traversal visits every node exactly once.

Space is O(h) where h is the height of the tree. The recursive call stack grows as deep as the tree height. For a balanced tree, h = log n. For a skewed tree, h = n. If you want O(1) space (ignoring the call stack), you can use Morris traversal, which threads the tree temporarily to avoid the stack. The recursive version is what most interviewers expect.

Building blocks

This problem is built on two fundamental building blocks.

Inorder traversal properties. The entire solution depends on the fact that a valid BST produces sorted output when traversed inorder (left, root, right). If you are not comfortable writing inorder traversal from memory, practice that first. Every BST problem uses this property in some form.

Violation detection in a sorted sequence. Once you have the inorder sequence, the problem reduces to finding two elements that are out of place. The pattern of tracking prev and comparing prev.val > current.val appears in many problems that need to find anomalies in what should be a sorted sequence. The key rule is: the first violation's larger node and the last violation's smaller node are the swapped pair.

# Inorder traversal skeleton for BSTs
def inorder(node):
    if not node:
        return
    inorder(node.left)
    # process node here (compare with prev)
    inorder(node.right)

# Violation detection pattern
if prev and prev.val > node.val:
    if not first:
        first = prev
    second = node

Edge cases to watch for

• Adjacent nodes swapped. Only one violation appears in the inorder sequence. The initial assignment of both first and second during the first violation handles this correctly.
• Root is one of the swapped nodes. The root can be swapped with any other node. The inorder traversal does not treat the root specially, so this case works automatically.
• Two-node tree. If the tree has only two nodes (root and one child) and they are swapped, there is exactly one violation. The algorithm sets first and second on that single violation and swaps them.
• Swapped nodes are leaf and internal node. No special handling needed. The inorder traversal compares values regardless of tree structure.

From understanding to recall

You now understand the full mechanics of recovering a BST: run an inorder traversal, detect violations where the previous value is greater than the current value, and identify the two swapped nodes from the first and last violations. The logic is clean and the implementation is short.

But will you remember the details when you see this problem in an interview? The specific pattern of setting first = prev on the first violation and second = node on every violation is easy to mix up if you have not practiced it recently. Which node is the "first" and which is the "second"? When do you update versus keep the original?

Spaced repetition locks in these details. You type out the solution from scratch at increasing intervals. The first few times you will need to think through the violation logic. After a few reps, the pattern becomes automatic: inorder traversal, track prev, first violation sets first to the larger node, every violation sets second to the smaller node, swap at the end.

Related posts

• Validate Binary Search Tree - Uses the same inorder traversal property to check if a BST is valid, the foundation this problem builds on
• Binary Tree Inorder Traversal - The traversal pattern that powers this solution, practice it until you can write it without thinking