The BST Deletion Bug That Took Three Days

I'd implemented recursive BST deletion twice before — once for a course, once just to see if I still remembered it. Both times it worked first try, which in hindsight should have worried me. This time I wanted the iterative version, no call stack, because the eventual target for this code is a microcontroller with about 2KB of stack and no patience for deep recursion.

The setup

Deleting a node with two children means finding its in-order successor (the smallest node in the right subtree), copying that value up, and then deleting the successor from wherever it actually lives. Recursively, the call stack keeps track of every parent pointer for you for free. Iteratively, you have to track them yourself.

So I tracked them myself:

node_t *parent = NULL;
node_t *cur = root;

while (cur && cur->key != target) {
    parent = cur;
    cur = (target < cur->key) ? cur->left : cur->right;
}

Standard stuff. The bug wasn't in finding the node. It was in what I did next.

What went wrong

For the two-children case, I found the successor, then re-pointed the successor's old parent's child pointer before copying the successor's key into the node being deleted:

/* wrong order */
splice_out_successor(successor, successor_parent);
target_node->key = successor->key;

splice_out_successor re-points successor_parent's child pointer past the successor — which is correct on its own. The problem is that when the successor happens to be the immediate right child of the node being deleted, successor_parent is target_node. Splicing out the successor first meant I was rewriting target_node->right using a stale copy of target_node I'd captured a few lines earlier for an unrelated bounds check. The pointer write landed, but on a version of the struct that no longer matched what was actually in the tree by the time the function returned.

The symptom was almost worse than a crash: the tree didn't corrupt immediately. It corrupted silently, and only showed up two or three deletions later as a lookup returning the wrong value. I spent the first day convinced the bug was in my lookup function, because that's where it became visible.

The fix

Copy the key up first, then splice out the now-redundant successor node using the tree's live state, not a captured reference:

/* correct order */
target_node->key = successor->key;                  /* copy first */
splice_out_successor(successor, successor_parent);   /* then splice it out —
                                                          target_node->key is
                                                          already safe */

Three days for what turned out to be a two-line reorder — the exact same two lines from the "wrong order" block above, just swapped. The fix itself took five minutes once I actually found it; the other two days and fifty-five minutes went into distrusting the wrong function.