Recover Binary Search Tree

Interview Prep

HardTrees Variation of Validate Binary Search Treetreesinorder

The problem

A valid binary search tree had exactly two of its node values accidentally swapped. The structure of the tree is otherwise unchanged. Restore the BST in place. Do not allocate a new tree.

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The key observation

An in-order traversal of a valid BST visits values in strictly increasing order. If exactly two values were swapped, the in-order sequence will have either one or two places where a value drops compared to its predecessor.

Two drops (non-adjacent swap): the misplaced values are at the larger position of the first drop and the smaller position of the second drop.
One drop (adjacent swap): both misplaced values are at the single drop — the predecessor and the current node.

The clean implementation captures both cases with one rule: on the first drop, record both the predecessor (the larger value) and the current node (the smaller value); on any later drop, just update the smaller value. At the end, swap their values (not the nodes themselves — the structure is fine).

Solution

def recover_tree(root: Node) -> None:
    """In-order traversal. Find the two nodes that are out of order; swap their values."""
    first = second = None
    prev = None
    def inorder(node):
        nonlocal first, second, prev
        if node is None: return
        inorder(node.left)
        if prev is not None and prev.val > node.val:
            if first is None:
                first = prev          # FIRST violation: keep the LARGER node
            second = node             # SECOND violation: the SMALLER node
        prev = node
        inorder(node.right)
    inorder(root)
    first.val, second.val = second.val, first.val

Trace

Tree (BST except that 3 and 1 have been swapped):

       3                Correct BST would be:        2
      / \                                            / \
     1   4                                           1   3
        /                                                \
       2                                                 4

In-order walk of the corrupted tree:
  visit 1, prev=None.  prev := 1.
  visit 3, prev=1 -> 1 < 3 ok.  prev := 3.
  visit 2, prev=3 -> 3 > 2 !  FIRST violation: first = 3, second = 2.
  prev := 2.
  visit 4, prev=2 -> 2 < 4 ok.  prev := 4.

Swap first.val (3) with second.val (2).  Tree is now valid.

Adjacent-swap case

Tree where the two swapped nodes are ADJACENT in the in-order sequence:

       3                Correct:        2
      / \                                / \
     1   2                               1   3

In-order walk: 1, 3, 2.
  1 < 3 ok.
  3 > 2  FIRST violation.  first = 3, second = 2.
  (No more nodes.)

Single violation in this case.  second remains correctly assigned because we
update it on EVERY violation; first is set only on the first one.

Complexity

Time: O(n) — single in-order traversal.
Space: O(h) recursion stack. Morris traversal reduces this to O(1) at the cost of more complex code.

Morris traversal for O(1) extra space

Morris traversal threads temporary right-pointers from each "predecessor in in-order" back to the current node, allowing in-order without a stack or recursion. The swap logic is identical; only the traversal mechanism changes. Useful when the interviewer pushes for constant extra space, but for most production use the standard recursion is fine.

Why swap values rather than nodes?

The tree's structure is correct — only the two values are misplaced. Swapping node values is one line. Swapping nodes (and re-pointing parent pointers) is fragile and unnecessary.