Recover a BST with two swapped nodes

Why this matters

A binary search tree depends on one rule: every value on the left of a node is smaller, and every value on the right is larger. A single wrong value breaks the rule for some searches, and a search for a value that is still in the tree can fail without any error message.

Sometimes the damage is small. Two values trade places, perhaps because of a bad copy, a bug in an update routine, or a file that was written in the wrong order. The tree still holds every value, and only two of them sit in the wrong spot. This lesson shows how to find those two values by reading the tree in order, and how to put them back.

The problem comes from a classic interview question. The method uses an inorder walk, which the earlier lesson on validating a BST and finding the successor already introduced. This lesson does not repeat that material. It only uses the fact that an inorder walk of a correct BST prints the values in increasing order.

The idea with a sorted list

Picture a row of numbered boxes on a table, sorted from left to right: 1, 2, 3, 4, 5, 6, 7. Now suppose someone secretly swaps the contents of two boxes, the one holding 2 and the one holding 6. The row now reads 1, 6, 3, 4, 5, 2, 7. You can see the problem by looking at the row. Two places where the order goes down are the clue. Those two places tell you which boxes to swap back.

An inorder walk turns the tree into exactly this kind of row. It visits the left subtree, then the node, then the right subtree. For a correct BST the output is sorted. For a broken BST the output looks like the row above. The job is to find the places where the sorted order goes down, and then decide which two values were swapped.

Step 1: build a tree and break it

Start with a correct tree. Insert the values 4, 2, 6, 1, 3, 5 and 7 in that order. The root is 4. The tree is a full tree of height 3, and its inorder walk prints 1 2 3 4 5 6 7.

Now break it on purpose by swapping the values in two nodes. The example swaps the node holding 2 with the node holding 6. The structure does not change. Only the two values change places, so node 2 now holds 6 and node 6 now holds 2.

Here is a complete program. It builds the tree, prints the inorder walk, swaps the two values, prints the broken walk, runs the repair, and prints the walk again. It also breaks a second pair of values that sit next to each other, to show a different case.

The output is:

correct:        1 2 3 4 5 6 7
broken:         1 6 3 4 5 2 7
recovered:      1 2 3 4 5 6 7
broken:         1 2 4 3 5 6 7
recovered:      1 2 3 4 5 6 7

Read the first broken line carefully: 1 6 3 4 5 2 7. The walk goes down twice. From 6 to 3 is one drop, and from 5 to 2 is the other.

The broken tree also fails at its job. Start a search for 6 at the root 4. The value 6 is larger than 4, so the search goes right, to the node that now holds 2. Since 6 is larger than 2, it goes right again, to 7. Since 6 is smaller than 7, it would go left, where there is nothing. The search reports that 6 is missing, even though the value is in the tree, in the wrong node.

Step 2: find the two drops

Look at each pair of neighbours in the broken walk:

• 1 then 6: going up, fine.
• 6 then 3: going down. This is the first drop.
• 3 then 4: going up, fine.
• 4 then 5: going up, fine.
• 5 then 2: going down. This is the second drop.
• 2 then 7: going up, fine.

The rule has two parts, and they are easy to remember:

1. The first drop tells you the bigger of its two values. Here that is 6. The bigger value was too early in the row, so it is the first value that must move.
2. The last drop tells you the smaller of its two values. Here that is 2. The smaller value was too late, so it is the second value that must move.

Swap 6 and 2 and the row reads 1 2 3 4 5 6 7 again. A swap of two values that are not next to each other always makes two drops, and the first one comes before the second one.

The adjacent case is simpler. In the walk 1 2 4 3 5 6 7 there is only one drop, from 4 to 3. The first drop gives the value 4, and the last drop, which is the same drop, gives the value 3. Swapping 4 and 3 fixes the row.

Step 3: write the walk that finds the drops

The program above keeps three pointers in a small struct called Fix. Here is what each one holds:

• prev is the node that the walk visited just before the current node. Its value is the previous value in the sorted order.
• first is the node for the bigger value of the first drop. It is set once, the first time a drop is found, and never changed after that.
• second is the node for the smaller value of the most recent drop. It is updated on every drop, so after the walk it holds the last one.

The function walk visits the nodes in inorder. At each node it compares prev with the current node. If prev is bigger, there is a drop. The code then does two things. It sets first if it is still empty, and it always sets second to the current node.

The repair function is short. It runs the walk, and then swaps the two values. The swap function from the <utility> header exchanges the values of two variables. Here the two variables are f.first->val and f.second->val. The arrows follow the pointers to the nodes, and the ->val part reads or changes the value stored in that node.

Why the program swaps values and not nodes

The fix changes the numbers inside the two nodes. It does not move the nodes around. The tree shape stays the same, and every link from parent to child keeps pointing to the same node as before. This is the simplest fix because the rest of the program keeps working with the same pointers.

A second way: the iterative walk

The recursive walk uses the call stack, which is the memory the computer uses to remember which function call is waiting for which. For a tree that is very tall, the recursion gets deep. A version with an explicit stack avoids that. It uses a vector that the program manages itself, so the depth is limited only by the memory available.

void recoverIterative(Node* root) {
    vector<Node*> stack;
    Node* prev = nullptr;
    Node* first = nullptr;
    Node* second = nullptr;
    Node* cur = root;
    while (cur || !stack.empty()) {
        while (cur) {
            stack.push_back(cur);
            cur = cur->left;
        }
        cur = stack.back();
        stack.pop_back();
        if (prev && prev->val > cur->val) {
            if (!first) first = prev;
            second = cur;
        }
        prev = cur;
        cur = cur->right;
    }
    swap(first->val, second->val);
}

The inner while (cur) loop walks down the left side and pushes each node onto the stack. When there is no more left side, the program pops the top node, which is the next node in inorder. Then it looks at the right side of that node. The rule for first and second is the same as before. On the same two broken lists this version prints the same recovered output as the recursive one.

A worked example with a tree of three

Take the smallest broken tree that is still interesting: a root of 2, with 3 on the left and 1 on the right. Its values are the wrong way round. The inorder walk is 3 2 1.

Walk it through the rule:

1. The first pair is 3 then 2. That is a drop. first becomes 3, and second becomes 2.
2. The second pair is 2 then 1. That is another drop. first stays 3, and second becomes 1.

Swap 3 and 1, and the walk reads 1 2 3, which is sorted. The example shows why both values are needed. Swapping 3 and 2 would give 2 3 1, which is still wrong.

A harder example: values far apart

Now take a tree of nine values, built by inserting 5, 3, 8, 1, 4, 7, 9, 2 and 6. Its inorder walk is 1 2 3 4 5 6 7 8 9. Suppose the values 1 and 9 were swapped. These are the smallest and the largest value, at opposite ends of the row, so this is the hardest case for a human to spot by eye.

The broken walk is 9 2 3 4 5 6 7 8 1. Apply the rule from the start:

1. The pair 9 then 2 is a drop. first becomes 9, and second becomes 2.
2. The pairs 2 3, 3 4, 4 5, 5 6, 6 7 and 7 8 all go up, so nothing changes.
3. The pair 8 then 1 is a drop. first stays 9, and second becomes 1.

The result is first equal to 9 and second equal to 1. Swapping them gives 1 2 3 4 5 6 7 8 9. The walk only needs one pass over the tree, and the code never has to look at the shape of the tree. It looks only at the order of the values as they come out.

Why one pass is enough

A single swap changes exactly two positions in the walk, and no other position. Every drop in the broken walk is therefore caused by one of the two moved values. The first drop has the moved big value on its left side, so its left value is the one that must go down. The last drop has the moved small value on its right side, so its right value is the one that must go up. Because the walk keeps only the first and last drops, it never needs to store the whole list.

Checking the repair

After a repair, check the result with the same walk. The list must be sorted, with each value smaller than the one after it. A short check is enough for a test: walk the tree in order, store the values in a vector, and compare each value with the next one. If any pair is not in increasing order, the repair failed, or the tree was not broken by a single swap.

This check does not tell you which two values were wrong. It only tells you the order is fixed. For a test, build a tree whose correct answer you already know, swap two values on purpose, run the repair, and compare the walk with the sorted list you expect. The program above does exactly this for two cases.

Common mistakes

Mistake 1: setting first on every drop

The most common error is to write first = prev; instead of if (!first) first = prev;. The line looks harmless, but it changes the answer. The next function overwrites first on every drop. Run it on the broken tree from step 1 and print the list before and after the repair.

void walkBad(Node* n, Node*& prev, Node*& first, Node*& second) {
    if (!n) return;
    walkBad(n->left, prev, first, second);
    if (prev && prev->val > n->val) {
        first = prev;
        second = n;
    }
    prev = n;
    walkBad(n->right, prev, first, second);
}

Its output is:

broken:    1 6 3 4 5 2 7
after:     1 6 3 4 2 5 7

The second drop, from 5 to 2, overwrote first, so the program swapped 5 and 2 instead of 6 and 2. The output is still wrong. The walk is no longer sorted: 1 6 3 4 2 5 7.

Mistake 2: running the repair on a tree that is already correct

If the tree has no drop, first stays nullptr. The line swap(f.first->val, f.second->val); then reads the value through a null pointer, which means a pointer that points to nothing. The program crashes.

Here is a correct three-node tree, with root 2, left 1 and right 3, run through the same walk and then swapped:

exit code 139

The program printed nothing. The cout output was still waiting in a buffer when the crash happened, so it was lost. An exit code of 139 means the program stopped with a segmentation fault, a crash caused by reading memory the program is not allowed to use. Guard the repair with a check such as if (f.first && f.second) before the swap, if the input might already be correct.

Mistake 3: forgetting that prev must be updated

If the line f.prev = n; is missing, prev stays nullptr, so the walk never sees a drop. first stays empty and the repair crashes, as in mistake 2. The code still compiles, so the bug only shows up when the program runs.

Mistake 4: using an uninitialized prev

C++ does not set a local pointer to nullptr for you. A pointer declared as Node* prev; holds whatever value was in that memory before, which can point anywhere. Always write an initial value, such as Node* prev = nullptr;, and check for it with if (prev && ...) as the code above does.

Mistake 5: swapping pointers instead of values

It is easy to write swap(f.first, f.second). That swaps the two pointers held in the struct, not the values inside the nodes. The tree is not changed at all, so the broken walk is printed again. Swap the val fields, which hold the numbers.

Practice

Exercise 1

The inorder walk of a broken BST is 1 2 7 4 5 6 3 8. Which two values were swapped, and what is the walk after the fix?

Show the answer

The drops are 7 then 4, and 6 then 3. The first drop gives 7, and the last drop gives 3. Swapping 7 and 3 gives 1 2 3 4 5 6 7 8, which is sorted. The two swapped values are 7 and 3.

Exercise 2

The inorder walk is 1 3 2 4 5. Name the value that first holds and the value that second holds.

Show the answer

There is one drop, from 3 to 2. So first holds the node with value 3 and second holds the node with value 2. Swapping them gives 1 2 3 4 5.

Exercise 3

The inorder walk is 5 4 3 2 1. Can this list come from swapping two values in a sorted list? Explain your answer.

Show the answer

No. A single swap of two values in the sorted list 1 2 3 4 5 can only make one or two drops, while this list has four drops in a row. The algorithm assumes exactly one swap, so on this input it would swap 5 and 1 and give 1 4 3 2 5, which is still wrong. Real input for this lesson always comes from one swap.

Exercise 4

Change the function recoverBST so it prints the two values it found, before the swap happens. Show the output for the tree 4 2 6 1 3 5 7 after the values 2 and 6 are swapped.

Show the answer

Add one line before the swap call inside recoverBST:

cout << "swap " << f.first->val << " and " << f.second->val << '\n';

The printed line is swap 6 and 2. The values come from the nodes the walk found, so they match the two values that were swapped.

Summary

• An inorder walk of a correct BST prints its values in increasing order.
• When two values are swapped, the walk shows one or two drops where the order goes down.
• The bigger value of the first drop and the smaller value of the last drop are the two values to swap.
• Set the first node only once, and update the second node on every drop.
• Swap the val fields of the two nodes. Do not swap the node pointers.