Tree Height Example (Another log n pattern)

A balanced binary tree with $n$ nodes has height $O(\log n)$. Why? Each level doubles the number of nodes.

Level $0$ has $1$ node (the root). Level $1$ has $2$ nodes. Level $2$ has $4$ nodes. Level $k$ has $2^k$ nodes. If the tree has $n$ total nodes, then $2^{h+1} - 1 \approx n$, so $h \approx \log_2(n)$.

This is why operations on balanced trees (like AVL trees or red-black trees) take $O(\log n)$ time. You traverse from root to leaf, which is $O(h) = O(\log n)$ steps.