In a binary search tree, deleting a key must preserve more than a sorted printout: all surviving subtrees must remain reachable, and a pointer-based implementation must respect its node-identity and memory-ownership contract.
1. The invariant and the two-child obstacle
Assume distinct keys and an ordinary binary search tree (BST): every key in a node's left subtree is smaller than its key, and every key in its right subtree is larger. Both child subtrees satisfy the same rule. Search follows one child after each comparison; its cost is controlled by the tree height, not automatically by the logarithm of the number of nodes.
A leaf can be removed directly. If a node has exactly one child, its parent can replace the node by that child; when the node is the root, the tree's root must change. With two children, neither child alone can simply replace the node without accounting for the other subtree. A useful replacement key is the inorder successor.
Definition 17.1.1
(Inorder successor of a node with two children)
Let be a node with a left and a right child in a BST of distinct keys. Its inorder successor is the node holding the minimum key of the right subtree of .
Lemma 17.1.2
(Position of the successor)
Let be the inorder successor of a two-child node . Then has no left child, every key in the left subtree of is smaller than the key of , and every other key in the right subtree of is larger than the key of .
Proof
(Minimality of the right subtree)
A left child of would hold a smaller key in the same right subtree, contradicting minimality, so has none. Every key in the left subtree is smaller than the key of , which is smaller than every key of the right subtree, in particular than the key of . The other keys of the right subtree are at least the minimum, and they differ from it because the keys are distinct, so they are larger.
Concept lensStructural
Deletion as a swap with the next key in sorted order
Read the tree through its inorder sequence, which lists the keys in increasing order. The successor is simply the next key after in that list. By the lemma it has no left child, so exchanging the key of with it turns the two-child deletion into the easy case of removing a node with at most one child.
The successor may have a right child, however, and that child must replace it at its old location. This case is easy to lose if a trace assumes that the minimum node is always a leaf.
Counterexample mode
The successor is not always a leaf
Claim: to delete a two-child node, copy the successor's key into it and unlink the successor by setting its parent's left pointer to null. Take root with left child and right child , where has children and , and has the right child . The successor of is , which is not a leaf. After copying into the root and setting the left pointer of to null, the node is no longer reachable, although was never deleted, and the inorder sequence has lost . The repair is to replace the successor by its right child, here , which the algorithm below does.
2. Return a new subtree root
Here is a recursive design. It uses left/right child pointers, no parent pointers, and returns the possibly changed root after every deletion. The stored record contains key and payload, not the node's child links. In the pseudocode, t.key abbreviates t.record.key. Assume copying a record yields an independent value that remains valid when the source node is freed; a real program with owned pointers needs an explicit deep-copy or ownership-transfer policy.
pop_min(t): // precondition: t != null
if t.left == null:
record = copy(t.record)
replacement = t.right
free(t)
return (record, replacement)
(record, t.left) = pop_min(t.left)
return (record, t)
delete(t, key):
if t == null: return null
if key < t.key:
t.left = delete(t.left, key)
else if key > t.key:
t.right = delete(t.right, key)
else:
if t.left == null:
replacement = t.right; free(t); return replacement
if t.right == null:
replacement = t.left; free(t); return replacement
(record, t.right) = pop_min(t.right)
t.record = record
return t
pop_min returns both a copied record and the root of the remainder. On unwinding, each caller reconnects its left child to that remainder. The deletion caller must assign the returned root, including at the top level: root = delete(root, key). Missing-key deletion reaches null and leaves the existing links unchanged. If an implementation keeps parent pointers or externally observable node references, it needs additional updates or a different identity policy.
Common mistake
(Ignoring the returned root)
Take a tree whose root has only a right child . The call delete(root, 5) frees the root node and returns . A caller that writes only delete(root, 5) and keeps the old root variable now holds a dangling pointer. The result must be assigned: root = delete(root, 5).
Common mistake
(Taking the maximum instead of the minimum of the right subtree)
In the tree of the first worked deletion below, the right subtree of the target has keys . If the code copies the maximum into the root and removes that leaf, the root becomes , yet the keys remain in its right subtree and are smaller than the root. The ordering is violated: a search for compares with , goes left into the subtree of , and fails. Only the minimum of the right subtree is smaller than all its other keys.
3. Worked deletions
Worked example 17.1.3
(A successor that is not a leaf)
Take root 40, with left child 20 (children 10,30) and right child 70 (children 50,80). Node 50 has right child 60. Delete key 40 using the value-copy rule above.
The minimum in the right subtree is 50, reached by 70 -> 50; it has no left child but has right child 60. pop_min returns record 50 and subtree 60 to its caller, so 70.left becomes 60. Copy the record to the original root node. The final root has key 50, left subtree rooted at 20 with children 10 and 30, and right subtree rooted at 70 with children 60 and 80. Its inorder sequence is 10,20,30,50,60,70,80: it contains exactly the original keys except 40.
The node that originally held 40 survives with a different record; the node that originally held 50 is freed. A client that treats node addresses as stable identities must not silently assume that copying keys implements deletion of the requested node. A transplant-based design can instead move the successor node, but must repair its old and new parent links and state which references remain valid.
Worked example 17.1.4
(The successor is the right child, and a missing key)
Take root 40 with left child 20 (children 10,30) and right child 70, where 70 has only a right child 80. Delete key 40. The right subtree has no left child at its root, so pop_min(70) takes the first branch: it copies record 70, returns replacement 80 and frees node 70. The caller sets 40.right = 80 and copies record 70 into the root, giving root 70 with left subtree 20 (children 10,30) and right child 80. The inorder sequence is 10,20,30,70,80, the original keys without 40. Deleting the key 99 from the original tree compares with 40, then 70, then 80, reaches null and returns each node unchanged.
Worked example 17.1.5
(Deleting the root when it has one child)
Let the tree have root 5 with only a right child 8. Then delete(root, 5) finds equality at the root, sees t.left == null, saves replacement = t.right, frees the root and returns 8. The new root is 8, with the same subtree below it. If instead the root had only a left child, the second branch would return that child. The tree's root variable changes in both cases, which is why the result of delete is assigned back.
4. Correctness and cost
Theorem 17.1.6
(Correctness of deletion)
Let be the root of a BST of distinct keys. Then pop_min(t), for null, returns the record of the minimum key and the root of a BST holding exactly the other keys. And delete(t, key) returns the root of a BST holding exactly the keys of other than key; if key is absent, the key set is unchanged.
Proof
(Induction on the height of the tree)
For pop_min: if t.left is null, the minimum is t.key, because the right keys are larger, and the remainder t.right is a BST of the other keys. Otherwise the minimum of is the minimum of the left subtree, since all left keys are below t.key; by induction, pop_min(t.left) returns it with a BST of the other left keys, and reconnecting that BST as the left child keeps all its keys below t.key.
For delete, argue by induction on the height. The null case returns null, correct because the key is absent. If the key is smaller than t.key, it can only occur in the left subtree; by induction the left subtree becomes a BST holding the same keys without it, and its keys are still all below t.key, so is a BST. The larger case is symmetric. If the key equals t.key and one child is null, the other subtree is itself a BST holding exactly the other keys. With two children, let be the successor. By the lemma, the left keys are below the key of , and pop_min leaves a right remainder holding the other right keys, all above it. Copying the record of into gives a BST whose keys are those of without the old key. In every case the returned subtree has keys within the bounds the old subtree had, since it only lost a key, so the ancestors' bounds still hold.
Proof X-ray
Where distinctness and minimality are used
Minimality of the successor is used twice: it makes the copied key larger than everything in the left subtree, and it makes every key left in the right remainder larger than the copied key. Distinctness turns "at least the minimum" into "strictly larger", which the BST rule demands. The returned-root convention is what lets the one-child cases and the root cases share one proof: each recursive call returns a subtree whose key set is known, so the parent only has to reconnect it. The induction closes because every call moves one level down.
Let h count nodes on a longest root-to-leaf path. Searching for the target, then descending to and removing its successor, visits O(h) nodes in total; returning through the recursion uses O(h) stack frames. On a chain, h can be n, so the worst-case time is O(n). A balanced height bound requires an additional balancing guarantee; an ordinary BST does not supply one. These costs assume constant-time key comparison, record copying and pointer updates, and a valid acyclic input tree.
5. Checks
Quick check
(In the tree of the first worked deletion, with still present, delete . What is the resulting tree and its inorder sequence?)
Find the minimum of the right subtree of .
Solution · Answer
The right subtree of is the single node , so the successor is and pop_min returns record and the empty remainder. The node that held now holds , has left child and no right child. The inorder sequence is 10,30,40,50,60,70,80.
Quick check
(In the same tree, delete . Which node becomes the successor, and what is the shape of the right part?)
The right subtree of is the node .
Solution · Answer
The successor is , a leaf. The node that held now holds , keeps its left child (with right child ), and loses its right child. The inorder sequence is 10,20,30,40,50,60,80.
Quick check
(Why must the caller write root = delete(root, key) rather than just calling delete(root, key)?)
Think of deleting the only node, or the root with one child.
Solution · Answer
The root node itself can be freed and replaced by one of its children or by null. Only the returned value identifies the new root; the old variable would dangle.
Quick check
(Insert in this order into an empty plain BST. What is , and how many nodes does delete(root, 4) visit?)
Draw the tree before counting.
Solution · Answer
The tree is a chain of right children, so nodes. The call compares with and then removes the leaf by returning its null right child, so it visits nodes, which is linear in .