Free Binary search trees lessonsBinary search trees · Stage 2 · Validate and repair · Step 2

Two values got swapped

Repair a search tree in which exactly two node values were swapped by mistake, by finding the two places where the inorder sequence goes down and swapping the values back. About 20 minutes.

Look for the drops

An inorder walk of a valid search tree gives increasing values. If two values were swapped, the list is almost sorted: one value is too big for its place and another is too small.

Walk inorder and compare each value with the previous one. A place where the previous value is bigger than the current one is a drop.

Inorder walk: should be increasing.

Drop: previous value bigger than the current one.

In code

prev = None
for v in inorder_values:
    if prev is not None and prev > v:
        print("a drop")
    prev = v

Inorder values of the broken tree 4, 6, 2, 1, 3, 5, 7, which should be 1, 2, 3, 4, 5, 6, 7.

6 follows 1: increasing. No drop.

Move 1 of 5

Which nodes to swap

Suppose the sorted values 1, 2, 3, 4 become 1, 4, 3, 2. The drops are 4 over 3 and 3 over 2. The wrong nodes are the 4, the earlier node of the first drop, and the 2, the later node of the last drop.

If the swapped values were neighbours, such as 1, 3, 2, 4, there is a single drop, 3 over 2, and the pair is that drop. The same rule works: the first node of the first drop, and the second node of the last drop. Swap their values.

First drop: remember its earlier node, once.

Every drop: remember its later node, overwriting.

In code

if first is None:
    first = prev      # the first drop
second = v            # the last drop

Quick check

An inorder sequence has two drops. Which two nodes are swapped?

AThe earlier node of the first drop and the later node of the second drop
BThe two nodes of the first drop
CThe two nodes of the last drop

Show the answer

The earlier node of the first drop and the later node of the second drop. The too-big value shows up early, and the too-small one shows up late.

Your problem

Recover a search tree

You are given the root of a binary search tree with different values in which exactly two nodes had their values swapped by mistake. Fix the tree by swapping the two values back, without changing the structure, and return the root.

Example

root = [3, 1, 4, null, null, 2] → [2, 1, 4, null, null, 3]

2 ≤ number of nodes ≤ 1,000 · different values · exactly two values swapped

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.