How Short Can a Tree Be?

Search, add, and remove each follow one path from the root toward the leaves. Search stops when it finds the value or reaches a null child. Add attaches a new leaf at the null spot where its search ends. Remove follows a path down to the node, and in the two-child case keeps going down the right subtree to the successor. A path is at most $h$ edges long, so each of these operations is $O (h)$ . That is the same reason one call to the iterator’s next is $O (h)$ .

That is not the same as $O (n)$ . A tree can hold many nodes and still be short. So the best shape is the shortest tree we can build from $n$ nodes. How short is that?

To keep a tree short, we want to fill each level completely before starting the next one. The fullest possible shape is a perfect binary tree: every internal node has two children, and every leaf sits at the same level.

Here are seven values in that shape:

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

Count the nodes level by level:

level 0: 1 node
level 1: 2 nodes
level 2: 4 nodes

Each level holds twice as many nodes as the one above it, because every node on a level has two children on the next level. Seven nodes fill exactly three levels, so the height is $2$ .

A perfect tree of height $h$ has levels of size $1, 2, 4, \dots, 2^{h}$ . Add them up:

n = 1 + 2 + 4 + \dots + 2^{h} = 2^{h + 1} - 1

Solve for the height:

h = lo g_{2} (n + 1) - 1 \approx lo g_{2} n

Check: $n = 7$ gives $h = lo g_{2} 8 - 1 = 2$ .

No binary tree is shorter

The same doubling puts a limit on every binary tree. Level $k$ can hold at most $2^{k}$ nodes, because each node has at most two children. So a tree of height $h$ holds at most $2^{h + 1} - 1$ nodes, the number in a perfect tree of height $h$ . To store $n$ nodes, a tree needs

n \leq 2^{h + 1} - 1 ⟹ h \geq lo g_{2} (n + 1) - 1

No binary tree of $n$ nodes can be shorter than about $lo g n$ . A perfect tree has exactly this height, because it fills every level. So on the shortest possible tree, search, add, and remove are $O (lo g n)$ .

The tallest possible tree

If every node has just one child, the tree is a single path:

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

Adding 20, 30, 40, 50, 60, 70, 80 in that order builds this tree. Each new value is larger than everything already in the tree, so it always goes right.

This is still a valid binary search tree, because every node’s right subtree holds only larger values, but it has the shape of a linked list. A tree with this shape is called degenerate. With $n$ nodes its height is $n - 1$ , so search, add, and remove are $O (n)$ in the worst case.