Searching for a Value

Search starts at the root. At each node, compare the target with the node’s value:

• If they are equal, the search has found the value.
• If the target is smaller, go left.
• If the target is larger, go right.
• If we reach null, the value is not present.

Here is the tree we will use for the rest of the chapter:

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

In the diagrams below, █ marks the node being compared, and ░ marks a subtree the search rules out without looking inside. A node already compared, such as 50 after the first step, goes back to a plain box.

Search for 60. Start at 50. The target is larger, so it cannot be in the left subtree; that rules out 30, 20, and 40 at once. Move right.

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

At 70, the target is smaller, so it cannot be in the right subtree; that rules out 80. Move left.

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

At 60, the target equals the node’s value, so the search has found it.

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

Search for 35. Start at 50. The target is smaller, so the whole right subtree is ruled out. Move left.

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

At 30, the target is larger, so move right. That rules out 20.

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

At 40, the target is smaller, so move left. But there is no left child. We reach null, so 35 is not in the tree.

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

Each comparison chose one subtree and discarded the other. So the search follows a single path down from the root. It never has to look at every node.