Tracing a Remove

This section traces the recursive remove as a call stack. We remove three values from one tree in a row, one for each case. Here is the starting tree:

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

Remove 40, a leaf

The search goes left at 50 and right at 30, so remove(50) and remove(30) are waiting. At 40 the first branch runs: node.left is null, so the call returns node.right, which is also null. remove(30) stores that null into 30.right, which unlinks the leaf, and returns 30. remove(50) stores 30 back into 50.left, unchanged. This unwinding works the same way as in the add trace, so here is only the tree after the removal:

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

Remove 30, one child

Removing 40 left 30 with a single child, its left child 20. The search descends left from 50 and finds 30.

call stack

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ remove(node=50)                   ┃
        ┃   waiting for remove(50.left, 30) ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

tree

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

The first branch is skipped, because node.left is not null. The second branch runs: node.right == null, so the call returns node.left, which is 20.

call stack

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ remove(node=30)                   ┃
        ┃   return 20  (one child)          ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌───────────────────────────────────┐
        │ remove(node=50)                   │
        │   waiting for remove(50.left, 30) │
        └───────────────────────────────────┘

tree

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

remove(50) stores 20 into 50.left. The only child takes the removed node’s place.

call stack

        (empty — all calls have returned)

tree

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

Remove 50, two children

50 is the root, so the search finds it right away. It still has both children, so neither of the first two branches applies. minNode(node.right) starts at 70 and follows left children to 60, which has no left child, so 60 is the successor.

Copy the successor value up with node.value = 60. There are two 60s now, so we have to remove the lower one.

call stack

        ┏━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ remove(node=60)    ┃
        ┃   node.value = 60  ┃
        ┗━━━━━━━━━━━━━━━━━━━━┛

tree

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

The line node.right = remove(node.right, 60) starts a nested removal in the right subtree. At 70, 60 is smaller, so we go left.

call stack

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ remove(node=70)                    ┃
        ┃   waiting for remove(70.left, 60)  ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌────────────────────────────────────┐
        │ remove(node=60)                    │
        │   waiting for remove(60.right, 60) │
        └────────────────────────────────────┘

tree

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

The lower 60 is found. It is a leaf, so the first branch returns null. Look at the stack: the original remove call for the root is still waiting at the bottom, and its node now holds 60.

call stack

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ remove(node=60)                    ┃
        ┃   return null  (leaf)              ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌────────────────────────────────────┐
        │ remove(node=70)                    │
        │   waiting for remove(70.left, 60)  │
        ├────────────────────────────────────┤
        │ remove(node=60)                    │
        │   waiting for remove(60.right, 60) │
        └────────────────────────────────────┘

tree

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

remove(70) stores null into 70.left, which unlinks the lower 60.

call stack

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ remove(node=60)                    ┃ ◀── receives 70
        ┃   waiting for remove(60.right, 60) ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

tree

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

The original call stores the updated right subtree into node.right and returns the node, now holding 60. The public method stores the returned node in root.

call stack

        (empty — all calls have returned)

tree

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