Trees, Branch by Branch

Why trees keep showing up

A sorted array lets you binary-search in $O(\log n)$ but insertion is $O(n)$ because every element after the insertion point has to shift. A linked list flips the trade: insertion is $O(1)$ at a known position, but search is $O(n)$.

A balanced binary tree gives you both in $O(\log n)$. That single fact — that you can support ordered insert and ordered search in the same logarithmic time — is the reason trees show up everywhere from database indexes (B-trees) to the priority queues inside Dijkstra and A* (binary heaps) to the rope structures that back modern text editors.

Anatomy

A binary tree is a collection of nodes, each carrying a value and up to two children — left and right. One node is distinguished as the root; a node with no children is a leaf; the height is the longest path from root to leaf.

• $n$ nodes means $n - 1$ edges. Always.
• A perfectly balanced tree on $n$ nodes has height $\lceil \log_2(n + 1) \rceil$.
• A degenerate tree (every node has at most one child, forming a "list") has height $n - 1$. Every operation degrades to $O(n)$. This is the worst case a BST will hit if you insert sorted data.
• A complete tree is filled level by level, left to right. Heaps are always complete — which is why you can store them in an array without wasting space.

Build a BST, search inside it

Type values one at a time. Each goes into the tree by the BST rule: smaller than current → go left; larger → go right; insert when you hit an empty slot. Then type a value to search for; the path is highlighted as it walks down.

Things worth trying:

• Click random 8 a few times. Most trees come out roughly balanced; height $\approx 3$ for $n = 8$.
• Click sorted 1..8. You get a right-spine — a linked list in disguise, height 7. This is exactly the worst case a real BST library protects against with balancing (AVL or red-black rotations).
• Search for a value that isn't there. You'll walk down until you hit a null and stop — the search path tells you where the value would be inserted.

Four traversals, one tree

A traversal visits every node exactly once. Four canonical orders, all defined by where the root sits relative to the recursive calls on its subtrees:

• Pre-order — root, then left, then right. Used to serialise a tree (knowing pre-order + in-order uniquely reconstructs it).
• In-order — left, root, right. On a BST, this yields the values in sorted order — the cleanest possible verification that your BST is correct.
• Post-order — left, right, root. Used to free / evaluate bottom-up (every parent waits for its children).
• Level-order (BFS) — visit by depth. Implemented with a queue, not recursion.

Pick a traversal below; the nodes light up one at a time in that order. Then look at the trail of values it produces.

The in-order traversal of a BST is a sorted list — try inserting unsorted values above and then running in-order here. It's the simplest BST sanity check.

Why balance matters

The cost of every BST operation — insert, search, predecessor, in-order successor, delete — is proportional to the depth of the node touched. A balanced tree caps depth at $\log_2 n$; an unbalanced one can let it grow to $n$.

Self-balancing BSTs solve this by rotating nodes whenever the height of two siblings drifts too far apart:

• AVL trees (Adelson-Velsky & Landis, 1962) keep $|h_{\text{left}} - h_{\text{right}}| \le 1$ at every node. Strict balance → fastest lookups, more rotations on insert.
• Red-black trees use a colour invariant that gives weaker balance but cheaper updates. This is what most standard libraries ship as their ordered map: C++ std::map, Java TreeMap, Linux kernel's process scheduler.
• B-trees generalise the idea to nodes with many children, tuned to disk-block sizes. Every relational database index you have ever used is a B-tree variant.
• Treaps and skip lists randomise to get balance in expectation without rotations — simpler to implement, comparable performance.

Heaps — parent dominates children

A binary heap is a complete binary tree with a single invariant: every parent is $\le$ both its children (min-heap) or $\ge$ both (max-heap). It is most naturally stored as an array — for a node at index $i$:

Because the tree is always complete, no array slots are wasted. Two operations preserve the invariant:

• Insert (sift-up). Append at the end; walk up swapping with parent while the invariant is violated. $O(\log n)$.
• Extract root (sift-down). Take the root (the min or max). Move the last element into the root slot. Walk down swapping with the smaller (or larger) child while the invariant is violated. $O(\log n)$.

Below: insert values into a heap and watch them sift up; extract the root and watch the last element sift down. Both the tree view and the array view stay synchronised.

Heapify — building a heap in O(n)

The obvious way to build a heap of $n$ items is to call insert $n$ times. That's $n \log n$ work. Floyd's heapify does it in $O(n)$ by working bottom-up.

Why $O(n)$ instead of $O(n \log n)$? Sift-down on a node at depth $d$ costs at most $h - d$ where $h = \lfloor \log_2 n \rfloor$ is the tree's height. Half the nodes are leaves (cost 0); a quarter are one level up (cost 1); an eighth are two levels up (cost 2); the sum collapses to a constant times $n$. Press heapify random 12 above and watch the bottom-up passes.

Heapify is also the building block of heap sort: build a max-heap in place ($O(n)$), then repeatedly extract-max into the last array slot ($n \log n$). Total $O(n \log n)$, in-place, no auxiliary memory. The reason it isn't the default sort in most languages is cache behaviour — quicksort and Timsort dominate in practice despite the same asymptotic.

Where this gets used

Sharp edges

• BST delete is the awkward operation. Inserting and searching are five lines each; deletion has three cases (leaf, one-child, two-children) and the two-children case requires finding the in-order successor. This is why textbooks devote a whole page to delete and a paragraph to insert.
• Heap does not support fast search. "Find an element in a heap" is $O(n)$. The heap invariant orders parents w.r.t. children only — not siblings. If you need both ordered iteration and priority extraction, you need two structures or a more elaborate one (indexed heap, treap, or balanced BST).
• Heap's decrease-key needs a handle. To decrease the priority of an arbitrary element you need to know its array index — which means a side hashmap keyed on element identity. Forget the side map and Dijkstra silently breaks.
• Pointer-based vs array-based. BSTs with explicit node objects pay for pointer chasing and poor cache locality. For small fixed-size trees, storing children in a flat array (left at $2i+1$, right at $2i+2$ — same trick as heaps) is much faster despite the gaps from unbalanced shapes.
• Recursion depth limits. A degenerate tree on $n$ nodes will overflow the call stack at $n \approx 10^4$ in most languages if you traverse with naïve recursion. Either balance the tree or use the iterative-with-explicit-stack form.
• Two heaps for the running median. A max-heap of the lower half and a min-heap of the upper half, kept balanced in size. Insert and median both cost $O(\log n)$. A classic interview question whose solution is a heap configuration, not a clever new structure.

Reading list

• Knuth, The Art of Computer Programming, Vol 3. The reference, still. Trees are chapter 6.2.
• Cormen, Leiserson, Rivest, Stein — CLRS. Chapters 6 (heaps), 12 (BSTs), 13 (red-black trees), 18 (B-trees). The teaching standard.
• Sedgewick & Wayne, Algorithms (4th ed.). Best presentation of red-black trees as left-leaning 2-3 trees.
• Adelson-Velsky & Landis, 1962 — An algorithm for the organisation of information. The AVL tree, the first balanced BST.
• Floyd, 1964 — Algorithm 245: Treesort. The bottom-up $O(n)$ heapify and heap sort in two pages.
• Bayer & McCreight, 1972 — Organisation and Maintenance of Large Ordered Indexes. B-trees.
• Pugh, 1990 — Skip Lists: A Probabilistic Alternative to Balanced Trees. A whole class of structures that argue against trees.