BST deletion

The problem it solves

Insertion into a binary search tree is the easy half of the contract: walk down, find the empty slot, attach. Deletion is where the structure earns its keep — remove a node from the middle of an ordered tree and the hole must close without disturbing the one property everything depends on: every left subtree smaller, every right subtree larger. Ordered maps, interval trees, database indexes — anything that promises both ordered iteration and removal is quietly running this routine.

Interviews love deletion for an honest reason: insertion can be recited, but deletion has cases, and the hardest case has a genuinely clever idea in it — the value being deleted is not unlinked at all; a stand-in value arrives from elsewhere in the tree and a different, easier node dies in its place. Whether a candidate can explain why the stand-in must be the inorder successor (or predecessor), and why deleting the successor never cascades, separates structural understanding from memorised walks.

The intuition — and where it breaks down

Three shapes of removal, in ascending order of thought required. A leaf just disappears — no children, no consequences. A one-child node is a link in a chain: splice it out and connect its parent directly to its only subtree, which is safe because that entire subtree sat on one side of it and keeps its relative order. The intuition that both of these are “pointer surgery with no thinking” is correct.

The two-children node is where the naive moves all fail. Promote the left child? Its right subtree now needs a home. Merge subtrees? That is a rebuild, not a deletion. The insight is to stop trying to move structure and move a value instead: the gap left by the deleted value sits, in sorted order, exactly between its left subtree and its right subtree. Precisely two values in the whole tree border that gap — the largest value of the left subtree, and the smallest value of the right (the inorder predecessor and successor). Copy either one into the node, and the ordering reads correctly again; then delete the donor from its old position. And the donor is guaranteed easy to delete: the successor is the leftmost node of the right subtree, so it cannot have a left child — its removal is always the leaf or one-child case. The hard case reduces to an easy case, once, with no recursion.

Where the intuition breaks: “copy a value” sounds like cheating — didn’t we want to delete a node? For a set-of-values structure the distinction is invisible. It stops being invisible when nodes carry identity beyond their key (iterators pointing at them, parent-pointer users, augmented data) — real implementations then splice the successor node structurally into the deleted node’s position instead of copying the value, same idea with more pointer surgery.

Loading…

A walkthrough you can check

Build a BST from [5, 3, 8, 1, 4, 7, 9] and delete 5, the root — a two-children case.

1. Find the successor: step right (to 8), then left to the wall (to 7). Stop — 7 has no left child, by construction.
2. Copy: the root’s value becomes 7. Read the inorder walk: 1, 3, 4, 7, 7, 8, 9 — a duplicate, briefly, which is why step 3 is not optional.
3. Delete the donor 7 from its old slot under 8: it is a leaf — unlink, done.
4. Final inorder walk: 1, 3, 4, 7, 8, 9. Sorted, with 5 gone.

Now the checks the player’s prompts push on. Why 7 and not 4 (the predecessor)? Both work — 4 is the largest of the left subtree; implementations pick one convention. Why not 8? Copy 8 up and the right subtree still contains 7 — which would sit right of the new root value 8 while being smaller. Only the two gap-adjacent values avoid this, and being able to say why is the whole exercise.

The invariant

After every deletion, the inorder traversal of the tree is exactly the previous traversal with the deleted value removed. The three cases preserve it for three different reasons. Leaf: removing a leaf deletes one element from the walk and touches nothing else. One child: the spliced subtree occupied a contiguous run of the walk adjacent to its parent; reconnecting it to the grandparent keeps that run in place. Two children: copying the successor creates a momentary duplicate adjacent in the walk (successor value now appears at the node and at the donor), and deleting the donor removes the second copy — net effect, the original value vanished, everything else kept its order.

The supporting lemma doing quiet work: the inorder successor of a node with a right subtree is that subtree’s leftmost node, and it has no left child. First part: everything in the right subtree exceeds the node, and the leftmost of it is the smallest such. Second part: if it had a left child, that child would be smaller and further left — contradiction. This lemma is why the reduction terminates in one step, and it is a legitimate interview question all by itself.

Complexity, derived

Every phase is a walk along one root-to-leaf path: finding the node is O(h); finding the successor is O(h) more (right once, then left down); the final splice is O(1) pointer work. Total O(h), with O(1) extra space for the iterative form — h the tree’s height.

The honest content is in what h is. Balanced tree: h = O(log n), and deletion is genuinely logarithmic. Degenerate chain (built from sorted input — the player’s sorted preset shows one): h = n, and deletion is linear. Plain BSTs make no promises about h, and worse, deletion actively erodes balance: always borrowing from the successor side thins the right subtrees over many operations, a measurable drift. This is the standing argument for self-balancing trees — AVL and red-black deletion run this same routine plus rebalancing on the walk back up, paying a constant factor to pin h at O(log n) forever.

What people get wrong

• A stand-in that is not gap-adjacent: copying any value other than the inorder predecessor/successor silently breaks the BST property — often in a way small tests miss, because the tree still looks fine.
• Recursing generally to delete the donor: the successor is guaranteed to lack a left child; its deletion is the easy case by construction. Handling it with the full routine works but signals the lemma was missed.
• Root deletions: the one-child splice at the root has no parent to re-point; forgetting to reassign the root pointer is the classic off-by-one-level bug — the trace’s early-value deletion exercises it.
• Duplicate handling: with duplicates stored (by convention, in the right subtree), “delete the value” versus “delete one instance” are different specs; know which one the interviewer means.
• Assuming deletion preserves balance: it does not; it degrades it. Say so before being asked.

Implementation notes

The iterative form needs a parent pointer (or a parent variable carried down the search); the recursive form threads the returned subtree root back up — node.left = deleteFrom(node.left, value) — and is shorter but allocates stack. Both appear in the sources panel with matched line numbering.

Copy-the-value versus splice-the-node: copying is simpler and right for value-set semantics; splicing preserves node identity for augmented trees (subtree sizes, interval maxima) — and in those trees, remember to walk back up recomputing augmentations after either variant.

Predecessor or successor? Either; alternating between them (or choosing randomly) measurably slows the balance drift on delete-heavy workloads — a nice detail to volunteer. And the reduction’s shape is worth restating as the takeaway: hard cases that reduce to easy cases already handled are a recurring design pattern — the same move appears in heap pops (last element stands in, then sifts) and union-find (path compression).

The follow-up questions

Why must the stand-in be the inorder successor or predecessor? The gap sits between the left subtree (all smaller) and the right (all larger); only the two values bordering the gap in sorted order can fill it without violating one side. Everything else is provably wrong, not just inelegant.

Why does deleting the successor never cascade? It is the leftmost node of the right subtree, so it has no left child; its own deletion is always the leaf or one-child case. The two-children case reduces exactly once.

What does repeated deletion do to the tree’s shape? Erodes it — consistently borrowing from one side skews the tree over time, degrading h. Self-balancing variants exist precisely because insertion and deletion both attack balance.

How does AVL/red-black deletion differ? Same three cases, then a rebalancing walk from the splice point back to the root — rotations (AVL) or recolour-and-rotate (red-black) restoring the height bound. The core deletion logic is unchanged; the extra work is what keeps h logarithmic.