Removing a Node with Two Children

Now remove 50, which has two children:

                ╭────╮
                │ 50 │
                ╰──┬─╯
        ┌──────────┴──────────┐
     ╭──┴─╮                ╭──┴─╮
     │ 30 │                │ 70 │
     ╰──┬─╯                ╰──┬─╯
   ┌────┴────┐           ┌────┴────┐
╭──┴─╮    ╭──┴─╮      ╭──┴─╮    ╭──┴─╮
│ 20 │    │ 40 │      │ 60 │    │ 80 │
╰────╯    ╰────╯      ╰────╯    ╰────╯

If we simply remove 50, both subtrees are left without a parent. We cannot replace 50 with 30, because 30 already has two children, so the right subtree rooted at 70 has no free child position under 30. We cannot replace it with 70 for the same reason on the other side.

So instead of moving a node into the place of 50, we keep the node and replace its value.

To remove a node with two children:

  1. Find its in-order successor.
  2. Copy the successor’s value into the node.
  3. Remove the successor from the right subtree.

The successor of 50 is 60, the minimum of its right subtree.

Copy 60 into the root:

                ╭────╮
                │ 60 │
                ╰──┬─╯
        ┌──────────┴──────────┐
     ╭──┴─╮                ╭──┴─╮
     │ 30 │                │ 70 │
     ╰──┬─╯                ╰──┬─╯
   ┌────┴────┐           ┌────┴────┐
╭──┴─╮    ╭──┴─╮      ╭──┴─╮    ╭──┴─╮
│ 20 │    │ 40 │      │ 60 │    │ 80 │
╰────╯    ╰────╯      ╰────╯    ╰────╯

Now there are two 60s. Remove the lower one from the right subtree rooted at 70. It is a leaf, so it can be removed directly:

             ╭────╮
             │ 60 │
             ╰──┬─╯
        ┌───────┴────────┐
     ╭──┴─╮           ╭──┴─╮
     │ 30 │           │ 70 │
     ╰──┬─╯           ╰──┬─╯
   ┌────┴────┐           └─┐
╭──┴─╮    ╭──┴─╮        ╭──┴─╮
│ 20 │    │ 40 │        │ 80 │
╰────╯    ╰────╯        ╰────╯

Now the tree is valid again. Two facts about the successor make this work.

First, the successor is the smallest value larger than the removed value. So it can sit after everything in the left subtree and before everything that remains in the right subtree.

Second, the successor is the leftmost node of the right subtree, so it has no left child. That means deleting it is never another two-child removal. The successor is either a leaf, or it has one child on the right.

We could also use the predecessor, the maximum value in the left subtree. It works symmetrically. We will use the successor by convention.