Delete a Node With Two Children

Replace the key with its in-order successor, then delete the successor from the right subtree.

Deleting a key from a binary search tree has three cases, decided by how many children its node has, and only the node with two children needs a plan. This card covers all three, step by step, with most of the time on the two-child case and the key that replaces it, the in-order successor.

A leaf has no children, so it is removed and its parent's link becomes empty. A node with one child is bypassed: the child moves up into its place, and the order holds because the child's whole subtree was already on the correct side of the parent. A node with two children cannot be bypassed, since its parent has one link to give and there are two subtrees to attach. Instead its key is overwritten by a key that fits exactly where it was, and that key is then deleted from lower down.

The key that fits is the in-order successor, the smallest key larger than the deleted one. It lies in the right subtree, at its leftmost node: go right once, then left until there is no left child. The steps delete 4, 6 and 1 from the tree of the keys 1 to 7 with 4 at the root, and show the lines a run printed.

The starting tree, with 4 at the root

4, two children: the case that needs a plan
- 2
  - 1
  - 3
- 6
  - 5, leftmost in the right subtree
  - 7

Deleting 4, then 6, then 1, with the tree after each delete

Find the successor of 4

4 has two children. Go right to 6, then left as far as possible: 6 has a left child, 5, and 5 has none, so 5 is the successor. No key lies strictly between 4 and 5.

text

4 has two children: go right, then left as far as possible: 6 -> 5

Copy 5 into the root

5 overwrites 4 in the root node. The order still holds there: 5 is larger than everything on the left, which was all below 4, and smaller than everything that remains on the right, because it was the smallest key there. For a moment 5 appears twice.

text

copy the successor 5 into the node that held 4

Delete the old 5 from the right subtree

The successor is the leftmost node of its subtree, so it never has a left child: removing it is always the leaf case or the one-child case. Here it is a leaf, and the left link of 6 becomes empty.

text

delete 5 from the right subtree:
  5 is a leaf: remove it
tree: 5(2(1, 3), 6(-, 7)) | in-order: 1 2 3 5 6 7

Delete 6, which has one child

6 now has only a right child, 7. The root's right link is pointed at 7, and 6 is gone. 7 was already larger than 5, so the order holds.

text

6 has one child, 7: the child takes its place
tree: 5(2(1, 3), 7) | in-order: 1 2 3 5 7

Delete 1, a leaf

1 has no children. The left link of 2 becomes empty.

text

1 is a leaf: remove it
tree: 5(2(-, 3), 7) | in-order: 2 3 5 7

The in-order listing after each step is the check: it stayed sorted and lost exactly the deleted key. A delete costs O(h), where h is the height, because finding the node and then its successor is at most one path from the root to a leaf.

The in-order predecessor, the largest key smaller than the deleted one and the rightmost node of the left subtree, works equally well. Either key sits next to the deleted one in sorted order, which is why it can take its place.

← → move through sections and cards