Removing a Leaf or a Single Child

To remove a value, first find its node. Then detach the node without breaking the ordering property. How we detach it depends on whether the node has no children, one child, or two children. This section handles the first two cases.

Case 1: a leaf

Remove 20 from the tree:

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

20 is a leaf, so removing it only means changing 30.left to null:

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

A leaf has no subtree below it, so no other node needs to be reattached.

Case 2: one child

Now use a slightly different tree:

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

Remove 30. It has one child, 40, so we splice 30 out by making 50.left point to 40:

      ╭────╮
      │ 50 │
      ╰──┬─╯
   ┌─────┴─────┐
╭──┴─╮      ╭──┴─╮
│ 40 │      │ 70 │
╰────╯      ╰──┬─╯
               └─┐
              ╭──┴─╮
              │ 80 │
              ╰────╯

That is safe because the child subtree stays on the same side of every ancestor. Everything below 30 was in 50’s left subtree, so it was smaller than 50, and after the splice it is still in 50’s left subtree.

The one-child case works the same way if the only child is on the left.