Tracing an Add

This section traces the recursive add as a call stack. We add 65 to the tree we have been using, so every call is add(node, 65).

Down the search path

The first call receives the root. At 50, 65 is larger, so the code runs node.right = add(node.right, 65). That call is now waiting for a result, and we move into 50’s right child.

call stack

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ add(node=50)                ┃
        ┃   waiting for add(50.right) ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

tree

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

At 70, 65 is smaller, so we go left into add(70.left, 65).

call stack

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

tree

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

At 60, 65 is larger, so we go right.

call stack

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

tree

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

The base case

60.right is null. The call add(null, 65) hits the base case: it creates the new node and returns it. Nothing is linked into the tree yet.

call stack

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ add(node=null)                          ┃
        ┃   return new Node(65)  (the empty slot) ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌─────────────────────────────────────────┐
        │ add(node=60)                            │
        │   waiting for add(60.right)             │
        ├─────────────────────────────────────────┤
        │ add(node=70)                            │
        │   waiting for add(70.left)              │
        ├─────────────────────────────────────────┤
        │ add(node=50)                            │
        │   waiting for add(50.right)             │
        └─────────────────────────────────────────┘

tree

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

Unwinding

add(60) receives the new node. It runs 60.right = <new node> and returns 60. This is the only assignment in the whole trace that changes the tree.

call stack

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

tree

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

add(70) receives 60, the same child it already had. It runs 70.left = 60, which does not change the link, and returns 70.

call stack

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

tree

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

add(50) receives 70, runs 50.right = 70, which again does not change the link, and returns 50. The public method assigns the returned node to root, and the tree now holds 65.

call stack

        (empty — all calls have returned)

tree

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