Adding a Value

To add a value to a binary search tree, start by searching for it. If the search finds the value, we do nothing, because the tree stores no duplicates. If the search reaches a null child without finding the value, that null spot is exactly where the new value belongs. Put a new node there.

Here is the tree again:

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

Add 35. The search for 35 in the section on searching went left at 50, right at 30, and left at 40, and stopped at 40’s empty left child, so the new node goes there:

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

A new value is always added as a leaf, and no existing node moves.

Why is that safe? The search path passes through every ancestor of the new spot. 35 went left from 50, so it is smaller than 50. It went right from 30, so it is larger than 30. It went left from 40, so it is smaller than 40. Those three comparisons are exactly what the ordering property asks of a node in that position. The new node has no children, so there is nothing below it that could break the property.

Compare this with a sorted array. There, adding means finding the insertion point and then shifting every later element one slot to open a gap, which is $O(n)$. In a binary search tree, adding just links in one new leaf.