Balance & Degeneration

## What the search actually does A binary search tree stores keys so that everything in a node's left subtree is smaller than the node and everything in its right subtree is larger. Searching exploits exactly that: compare the target with the current node's key, and if it is smaller descend left, if larger descend right, otherwise stop. Each comparison eliminates one subtree and moves you down exactly one level. So the work done by a lookup is *the number of levels it descends*. In the worst case for a given tree that is the tree's **height** `h` — the number of edges (or nodes, depending on convention; the asymptotics are the same) on the longest root-to-leaf path. Hence the cost statement: **search, insert and delete are all O(h)**, because all three are built on the same downward walk. ## Why h is not the same thing as log n `log n` is what the height *would* be if every level were full — a bushy tree, where each level roughly doubles the node count, so `n` nodes fit into about `log2 n` levels. That is the best case, and it is where the familiar "halve the search space each step" intuition comes from. But a plain binary search tree has no mechanism that produces that shape. It has an *ordering* invariant, not a *shape* invariant. Insertion walks down to the first empty slot and hangs the new node there; nothing measures the height, nothing moves existing nodes. The resulting shape is a pure function of the order the keys arrived in. The two extremes: | Insertion order | Resulting height | Lookup cost | |---|---|---| | Ideal / bushy | about log2 n | O(log n) | | Uniformly random | Θ(log n), with a larger constant | O(log n) | | Strictly ascending or descending | n | O(n) | The last row is the one that matters in practice. Insert 1, 2, 3, 4, 5 in that order: 1 becomes the root; 2 is greater, so it becomes 1's right child; 3 is greater than both, so it becomes 2's right child; and so on. Every node has exactly one child, all on the same side. Structurally this is a linked list that also happens to pay for two child pointers per node. A million ascending inserts give you a chain a million nodes long, and a lookup for the largest key touches every one of them. Notice what has *not* broken: the ordering invariant still holds, an inorder traversal still yields the keys in sorted order, and every operation still returns the right answer. Degeneration is a **performance** failure, not a correctness one, which is precisely why it survives code review and unit tests and shows up later as a latency problem. ## Reading the bound correctly Three directions people get backwards: 1. **O(h) is an upper bound on one operation, not a promise about a shape.** It says a lookup never costs more than the height; it says nothing about what the height is. 2. **h ranges over `[about log2 n, n]`.** Both ends are reachable with ordinary data, so quoting either end alone as "the" complexity is wrong. 3. **The tree does not repair itself.** A plain BST that has degenerated stays degenerated; subsequent well-mixed inserts hang off the chain rather than fixing it. The balanced-tree families — AVL, red-black, and the B-tree family — exist exactly to close this gap. They add bookkeeping so that writes maintain a *height bound* as well as the ordering, converting O(h) into a genuine O(log n) worst case. You pay for it with extra per-node state and extra work on every insert and delete. When someone asks why balanced trees exist at all, the answer is this leaf: because in a plain BST, `h` is chosen by your input, not by you. ## How to say it in an interview "Lookup is O(h), one node per level. Height is between about log2 n and n, and which one you get depends entirely on insertion order — sorted input gives you a chain and O(n). If I need a worst-case bound rather than a hope, I use a self-balancing tree." That sentence contains the whole idea, and it is the answer the O(h) phrasing is fishing for.