Tracing a Search

This section traces the two searches from the section on searching, the one for 60 and the one for 35, as call stacks. Every call is contains(node, value).

A successful search: find 60

The first call gets the root. At 50, 60 is larger, so the code runs return contains(node.right, value) and we go right.

call stack

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

tree

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

At 70, 60 is smaller, so we go left. A second frame stacks on top.

call stack

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

tree

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

60 matches, so this call returns true.

call stack

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

tree

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

contains(70) receives true and returns it unchanged, and so does contains(50). The public method returns true.

An unsuccessful search: find 35

Now search for 35, which is not in the tree. The search stacks contains(50), contains(30), and contains(40), along the same path shown in the section on searching. At 40 it goes left, and the call contains(null) reaches the base case and returns false:

call stack

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ contains(node=null)                 ┃
        ┃   return false  (fell off the tree) ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌─────────────────────────────────────┐
        │ contains(node=40)                   │
        │   waiting for contains(40.left)     │
        ├─────────────────────────────────────┤
        │ contains(node=30)                   │
        │   waiting for contains(30.right)    │
        ├─────────────────────────────────────┤
        │ contains(node=50)                   │
        │   waiting for contains(50.left)     │
        └─────────────────────────────────────┘

tree

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

The false passes back up through contains(40), contains(30), and contains(50) unchanged, the same way the true did. The public method reports that 35 is absent.

Each search made one call for each node on its path, plus one call on null when the value was absent. The true or false came back up unchanged, and nothing in the tree changed.