3.13

In an in-order walk of a Binary Search Tree (BST) the keys must appear in ascending order. If exactly two keys are swapped, the in-order sequence will contain at most two “inversions”, i.e. places where a previous key is larger than the current key.

Algorithm (O(n) time, O(h) stack space, or O(1) with Morris traversal):
1. Traverse the tree in-order while remembering the last visited node prev.
2. Whenever prev.val > curr.val we have an inversion. • On the first inversion, record first = prev and second = curr. • On a possible second inversion, update only second = curr (leave first unchanged).
3. After the traversal first and second are the misplaced nodes. Swapping their values restores the BST.

def recover_bst(root): first = second = prev = None stack = [] node = root while stack or node: while node: stack.append(node) node = node.left node = stack.pop() # detect inversion if prev and prev.val > node.val: if not first: first = prev second = node prev = node node = node.right if first and second: first.val, second.val = second.val, first.val

Why it works: an in-order traversal of a correct BST is sorted. Swapping two nodes introduces 1 (adjacent keys swapped) or 2 (non-adjacent) inversions. The procedure above records the first element of the first inversion and the second element of the last inversion, which are precisely the two misplaced nodes, and touches every node once ⇒ O(n).

Back to Chapter 3