Binary Search Tree (BST) — BST property, insert, search, delete (3 cases): Visual walkthrough

Step 0 — The one rule everything hangs on

Before we delete anything, let us lock in the picture we will keep pointing back to.

Figure — Binary Search Tree (BST) — BST property, insert, search, delete (3 cases)

Look at the picture. The blue node is $50$ . Every number in the orange (left) blob is below $50$ ; every number in the green (right) blob is above $50$ . That is the invariant we must never break, no matter what we delete. Deleting is only "hard" when it threatens this rule.

Let us build our running tree once and reuse it:

$50 \to 30, 70 \to 20, 40, 60$

Read this as: $50$ is the root; $30$ sits left of it, $70$ right of it; then $20, 40$ hang under $30$ and $60$ hangs under $70$ . In-order walk (left → node → right) gives $20, 30, 40, 50, 60, 70$ — sorted, so it is a valid BST.

Step 1 — Finding the victim (every delete starts here)

WHAT. To delete key $v$ , first walk down to it using the exact same rule as search: if $v < k$ go left, if $v > k$ go right, if $v = k$ you found it.

WHY. We cannot fix a node we have not located. And the walk is free information: it also tells us who the parent is, which we will need to re-wire pointers.

PICTURE. Below, the red path is the walk for deleting $v = 20$ : $50 \to 30 \to 20$ . Each step throws away one whole subtree (the greyed-out blobs) because the rule promises $v$ cannot be there.

Once we arrive at the victim node, how many children it has decides everything. There are exactly three possibilities: 0, 1, or 2. That is where the "three cases" come from — nothing more mysterious than counting arrows.

Step 2 — Case 1: the leaf (0 children)

WHAT. The victim has no children (both arrows point at None). Just cut it off: set its parent's arrow to None.

WHY. A leaf holds no subtree, so removing it orphans nobody. Nothing below it needs re-parenting, so the invariant cannot break.

PICTURE. We delete $20$ (a leaf under $30$ ). The red $\times$ removes it; $30$ 's left arrow simply becomes None.

Step 3 — Case 2: one child (splice it out)

WHAT. The victim has exactly one child (one arrow to a real node, the other to None). Delete the victim by hooking its single child directly to its parent — the child "moves up" one level.

WHY. Here is the key insight: that lone child subtree is already on the correct side of every ancestor. The victim was just a pass-through box. Removing the box and joining the pipe keeps every ancestor's left/right relationship intact.

PICTURE. Suppose $70$ has only a left child $60$ (imagine $70$ 's right arrow is None). Delete $70$ : the orange arrow that used to be " $50 \to 70$ " now becomes " $50 \to 60$ ". The child $60$ was already $> 50$ , so $50$ 's right side stays valid.

Step 4 — Case 3, the problem: two children

WHAT. The victim has both a left and a right child (two real subtrees). We cannot splice — there are two pipes, not one, and the parent has only one arrow to give.

WHY it's hard. Look at the picture: if we naively delete $50$ , both the orange blob (all $< 50$ ) and the green blob (all $> 50$ ) are orphaned. Whoever takes $50$ 's spot must be a single key that keeps both blobs valid at once.

Step 5 — Case 3, the fix: the in-order successor

WHAT. Copy the successor's key up into the victim's box. Then delete the successor from the right subtree.

WHY it's the perfect replacement. The successor $s$ is bigger than every left-blob key (it lives in the right subtree, which is all $> 50$ ). And it is the smallest right-blob key, so it is smaller than everything else remaining on the right. It fits the razor-thin slot exactly — both subtrees stay legal.

PICTURE. For deleting $50$ : go right to $70$ , then left to $60$ (leftmost). $60$ is the successor. Copy $60$ into the root box; the root now reads $60$ . Then delete the old $60$ node — which is a leaf, so we are back to Case 1.

Step 6 — The degenerate & edge cases (never leave a gap)

Every real implementation must survive the weird inputs. Here they are.

Deleting a key that isn't there. The walk hits None and returns None up the chain — the tree is unchanged. No crash, no-op.

Deleting the root when it's the only node. Root is a leaf → Case 1 → the whole tree becomes None (empty tree). Callers must accept "empty" as a valid result.

The two "no left child" shortcut. In code, if root.left is None: return root.right cleanly handles both the leaf case (right is also None, so it returns None) and the one-right-child case — one line, two cases. Symmetrically if root.right is None: return root.left.

The one-picture summary

This single diagram is the whole delete algorithm: locate the victim, count its children, and branch into 0 / 1 / 2. The two-child branch reduces to a smaller delete via the successor, so ultimately every delete bottoms out at a leaf or one-child splice.

Recall Feynman retelling — say it in plain words

To delete a number from a BST, first walk down to it the same way you'd search, comparing at each step and dropping half the tree. When you arrive, count its children. No children? Snip it — it was a dead end, nothing below it to save. One child? That child was already sitting on the correct side of everyone above, so just pull it up into the gap; the pipe reconnects cleanly. Two children? You can't pick a side, so instead of moving nodes you swap a key in: grab the smallest number in the right subtree (walk right once, then left until you can't) — it's the one number that's bigger than the whole left half and smaller than the rest of the right half, so it fits perfectly. Paste that number into the spot, then delete its original node — which, being the leftmost of a subtree, has no left child, so it's an easy Case 1 or 2. Weird inputs: deleting a missing key does nothing; deleting the last node leaves an empty tree. Every path ends at a simple snip.

Recall Predict before peeking

Why are there exactly three cases, and not four? ::: Because a binary node has at most 0, 1, or 2 children — you're just counting arrows. Two children is the only case that can't splice. Why must the replacement in Case 3 be the smallest key on the right (not any right key)? ::: It must sit just above the whole left subtree and below the rest of the right subtree; only the minimum of the right subtree squeezes into that gap. Why can deleting the successor never trigger another two-child case? ::: The successor is the leftmost node of the right subtree, so it has no left child — at most one child, i.e. Case 1 or 2. What does return root.right accomplish when root.left is None? ::: It handles leaf (returns None) and single-right-child (returns that child) in one line.

See also: Binary Tree — terminology & traversals, Recursion on Trees, Binary Search on Sorted Array, Heap vs BST.