STEP 14 · BINARY SEARCH TREES · REDUCE THE HARD CASE TO THE EASY ONE · MEDIUM

Delete Node in a BST

WHAT IT SAYS

Remove the node holding a given key from a BST, keeping the tree a valid BST.

WHAT IT'S REALLY ASKING

"Zero children: unhook it. One child: splice the child through. Two children is the case that looks hard — until you ask who could sit in this seat without breaking order. Exactly two candidates exist: the largest value on the left, or the smallest on the right. And here is the gift: each of those candidates has AT MOST ONE child, so evicting it from its old position is one of the easy cases. The hard case doesn't get solved — it gets demoted."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Rebuild the tree without the key

O(n) time minimum, O(n) space, and the original structure is discarded

Traverse the whole tree collecting every value except the target, then construct a fresh BST from the collection — insert one by one, or sort and build.

WHERE THE WORK IS WASTED — Deletion is a LOCAL event — one node leaves, and the ordering relations among all other pairs are untouched — but rebuilding treats it as global catastrophe, re-deriving n-1 nodes' worth of structure that was never in question. Worse than the time is what gets destroyed: the tree's existing shape (and any balance it had) is thrown away, subtree references held elsewhere dangle, and an O(h) pointer adjustment has been inflated into an O(n) reconstruction. The blast radius of removing one node is that node's immediate neighbourhood; everything beyond it is collateral damage you invented.

KEY OBSERVATION — THE UNLOCKlink

The successor never has a left child.

Walk the three cases in order of what they teach. No children: the node's absence needs no repair — null out the parent's pointer. One child: the node was a waypoint on a single path; splice the child into its place, and every ordering relation is preserved because the child's entire subtree already lived on the correct side of every ancestor. Both cases are pure pointer moves, O(1) beyond finding the node. Two children is where the structure fights back: neither child can simply take the seat, because promoting the left child orphans the right subtree and vice versa. So ask the question that dissolves it: which VALUE could occupy this position and keep every comparison in the tree correct? The seat's constraints are 'greater than everything in the left subtree, less than everything in the right'. Only two values in the tree satisfy that: the maximum of the left subtree (the inorder predecessor) or the minimum of the right subtree (the inorder successor) — the values immediately adjacent to the departing key in sorted order. Adjacency is exactly why they fit: nothing in the tree lies between them and the deleted key, so no comparison can distinguish them from it. Now the fact that turns a swap into a full algorithm: the minimum of the right subtree is found by walking left from the right child until left turns run out — so by construction IT HAS NO LEFT CHILD. Symmetrically the left subtree's maximum has no right child. The candidate is always a zero-or-one-child node. So the procedure is: copy the successor's value into the seat, then delete the successor from where it was — and THAT deletion is guaranteed to hit one of the two easy cases. The two-child case never recurses into itself; it fires exactly once and hands off. This is reduction, not recursion: the hard case's entire job is to transform itself into an easy case somewhere deeper.

Search, then case-split, with the two-child case delegating

O(h) time — one descent to find, at most one more descent to the successor — O(h) recursion or O(1) iterative

Recursively descend by comparison until the key matches. Zero or one child: return the other child (possibly null) to the parent's pointer — the reassignment idiom handles both at once. Two children: find the right subtree's minimum, copy its value into the current node, then recursively delete that value from the right subtree, knowing it lands in an easy case.

WHAT YOU TRADED — Copying the successor's VALUE rather than relocating the node is what keeps the pointer surgery trivial — the cost is that node identity isn't preserved (external references to the successor node now hold a different key), which matters in systems where nodes carry identity beyond their key. And as with insertion, repeated deletion erodes balance with no compensating mechanism — the self-balancing trees pay rotations to buy that back. The transferable lesson: when one case of a problem is hard, look for a transformation that maps it onto the cases you have already solved — reduction beats head-on solution.

WATCH THE IDEA RUN

deleting 3

two children ⇒ reduce to the one-child case

A node with 0 or 1 child is easy — splice it out and hand its only child to its parent. The hard case is TWO children: you cannot promote both, and the hole has to be filled by someone.

step 1 / 8

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Demote the Hard Case

YOU'LL SEE IT AGAIN WHEN

The operation splits into cases by local structure, and all but one case are trivial pointer moves.
The hard case has a canonical substitute element — the inorder-adjacent value — whose own removal provably lands in a trivial case.
The substitute is located by a degenerate walk (all-left or all-right), which is what guarantees its child count is deficient.

SAME BLUEPRINT, DIFFERENT PROBLEM

Insert into a BSTInorder Successor in BSTKth Smallest Element in a BSTRemove Nth Node From End of List (splice-through as the easy case)

The bar isn't "solved it once." It's "could rebuild it from the observation."