The tree that is a list

A binary search tree supports lookup, insertion and deletion in $O(\log n)$ time.

That sentence is in every data structures course and it is false for the plain unbalanced tree, in a specific way that matters: it is true if the keys arrive in a reasonably random order and catastrophically false if they arrive sorted.

Build a tree by inserting the keys 0, 1, 2, …, 62 in that order. Every key is larger than everything already present, so every insertion goes right. The result has height 62. It is a linked list wearing a tree’s data structure, and a lookup walks the whole thing.

The failure is total, not partial #

The important feature is that this is not a case of the structure being somewhat worse than advertised. It is as bad as it is possible to be.

For $n$ sorted keys the height is exactly $n - 1$: not $2\log n$, not $\sqrt{n}$, but the theoretical maximum for a tree with $n$ nodes. Every single insertion after the first descends the entire existing structure. The total cost of building the tree is $\frac{n(n-1)}{2}$ comparisons — the same as selection sort, from a structure chosen specifically to avoid that.

The site’s gate asserts the exact equality rather than an inequality. assertSortedInputDegenerates requires a tree of $n$ sorted keys to have height exactly $n-1$, because “worse than logarithmic” would be satisfied by a tree of height $3\log n$, and the claim being made is much stronger than that.

It also requires the shuffled tree to be genuinely logarithmic — height under $3 \log_2 n$ — because if both trees degenerated, the comparison would be showing nothing about insertion order.

And sorted input is what arrives #

The reason this is a practical problem rather than a curiosity is that sorted insertion order is not an adversarial special case. It is the default.

Data arrives sorted constantly: rows read from a database in primary-key order, timestamps from a log, IDs from a sequence, results of a previous sort, keys read from a file that somebody sorted for readability. A structure whose worst case is “the data was already in order” has its worst case aligned with one of the most common situations there is.

Nearly-sorted is nearly as bad, and that sentence is worth replacing with a measurement, because “nearly as bad” understates it.

Take the keys 0 to 1,022 in order and disorder them by swapping adjacent pairs at random — the mildest scrambling available, and roughly what a stream of mostly-ordered records looks like. Build the tree from the result:

A perfectly balanced tree of 1,023 nodes has height 9.

The last two rows are the ones that matter. Swapping five hundred adjacent pairs in a thousand-element sequence produces something that no reader would call sorted — half the positions have been disturbed — and the tree it builds has height 734 and a mean lookup depth of 370. That is 72% of the fully degenerate height and thirty-four times the fully shuffled one. The structure has recovered essentially none of its logarithmic behaviour.

The reason is that depth is decided by long-range structure and adjacent swaps only create short-range disorder. A node ends up shallow when it arrives early and splits the remaining key range into two substantial halves. Swapping neighbours never moves a key more than one position, so no key ever arrives early relative to keys far from it, the ascending spine survives intact, and the tree is a list with a few two-node bumps hanging off it.

So “nearly sorted” is not a point partway between sorted and random. Sortedness and the property a BST needs are not the same axis, and a stream can be substantially disordered by every local measure while being, for this structure, indistinguishable from sorted. The distributions that break this structure and the distributions that look broken to a person are different sets.

That also disposes of a tempting defence: that real data is never exactly sorted so the pathological case is rare. The pathological case is not exact sortedness. It is any insertion order whose long-range trend is monotone, and that describes timestamps, sequence IDs, paginated exports and the output of a previous sort — all of which contain plenty of local jitter and none of the global disorder the structure needs.

This is the same shape of problem as quicksort with a first-element pivot, and for the same underlying reason: both algorithms use the incoming order as a proxy for structure, and sorted input makes that proxy maximally uninformative. The two standard fixes are also the same — randomise, or rebalance.

What the numbers are #

Inserting the keys 0 to 127:

The ideal is $\lfloor \log_2 128 \rfloor = 7$: a perfectly balanced tree of 128 nodes.

The shuffled tree’s height of 13 is nearly twice the ideal, and that factor of two is not sloppiness in the shuffle. It is a known result: the expected height of a binary search tree built from a random permutation is about $4.31 \ln n$, or roughly $3 \log_2 n$. Random trees are logarithmic and they are not balanced — the constant is genuinely three times the ideal, and a balanced tree structure buys that factor back.

The build cost difference is a factor of 10.4 at $n = 128$ and grows: at $n = 1{,}024$ it would be about 50, and at $n = 10^6$ about 25,000.

Those two build costs are quicksort’s two cases #

The 8,128 and the 778 in that table are not merely similar to quicksort’s numbers. They are the same quantity, and the correspondence is exact rather than an analogy.

Inserting a key into a binary search tree costs one comparison per level descended, so the total cost of building the tree is the sum of every node’s depth — the tree’s internal path length. Now consider quicksort run on the same permutation, taking each subarray’s first element as its pivot. The first pivot is the tree’s root. Everything less than it goes left, everything greater goes right, and each side is then partitioned by its own first element, which is that subtree’s root. The recursion tree of quicksort and the binary search tree are the same tree, built by the same decisions in the same order.

That gives the bijection: quicksort compares two elements exactly when one is an ancestor of the other, because a pair is compared once, at the moment the shallower of them serves as pivot, and never again afterwards. So quicksort’s comparison count is the number of ancestor–descendant pairs, which is the sum of the depths, which is the build cost. The two algorithms are one algorithm counted twice.

Everything in the table follows from that.

The sorted tree’s $\frac{n(n-1)}{2}$ is not merely reminiscent of quicksort’s worst case; it is quicksort’s worst case, arising from the same input for the same reason — the pivot is an extreme value at every level and the partition removes one element. The shuffled tree’s height and cost are quicksort’s average case. And the expected mean depth of a random tree, $1.39\log_2 n$, carries the same constant as the $1.39\,n\log_2 n$ expected comparisons of randomised quicksort, because the second is $n$ times the first by construction.

Two things follow that are worth having.

The first is that what randomising the pivot buys and what shuffling the insertion order buys are one measurement, so a reader who has the sorting result already has this one. The essays were written separately and the underlying fact is single.

The second is a caution about the floor. Comparison sorting cannot go under $\log_2 n! \approx 1.44\,n\log_2 n$ comparisons, established in the floor under every comparison sort — and a perfectly balanced tree has internal path length about $n\log_2 n$, which is below it. There is no contradiction, because building the balanced tree from an arbitrary permutation is what would cost the extra: the balanced tree is the answer, not the search for it. A structure’s shape can beat a bound that its construction cannot.

What balancing actually buys #

A self-balancing tree — AVL, red-black, or any of the others — maintains an invariant that forces the height to stay within a constant factor of $\log n$ regardless of insertion order.

Measured against the two cases above, balancing buys:

• against the sorted case, a factor of about $n / \log n$ — 18 at $n = 128$, and unbounded as $n$ grows
• against the shuffled case, a factor of about 2 to 3

That second number is the interesting one, because it is what balancing costs when the data was going to be randomly ordered anyway. Rotations are not free — every insertion may perform one or two, each touching several nodes and their pointers — and against random input that overhead buys an improvement to a height that was already logarithmic.

So the case for balancing is not “it makes trees faster”. It is that it converts a claim about the data into a guarantee, and guarantees are worth paying for precisely when the input is out of one’s control. The distinction is the same one as amortised versus worst case: the average was always fine, and what is being bought is the elimination of the tail.

Why the layout makes it obvious #

The trees above are drawn with each node’s horizontal position given by its rank in the in-order traversal, and its vertical position by its depth. That is the standard layout, and it is worth saying why it is the right one here.

Under it, a balanced tree looks like a triangle and a degenerate tree looks like a diagonal line. The difference is immediate and it is not a drawing convention imposed on the data — the diagonal is a direct consequence of every node having exactly one child, since each successive node is one rank further right and one level further down.

A layout that placed children at fixed offsets from their parents would make the degenerate tree look like a diagonal too, but it would also make a balanced tree of any size look like a triangle of the same shape, and the two would be harder to compare at a glance. The in-order layout puts both trees on the same horizontal scale, so the vertical extent is directly comparable, which is the quantity the essay is about.

Why the mean depth matters more than the height #

The height is the worst-case lookup cost and it is the number usually quoted. The average lookup cost is the mean depth over all nodes, and for the degenerate tree the two are related in a way worth knowing.

A tree of $n$ sorted keys has height $n-1$ and mean depth $\frac{n-1}{2}$ — every lookup averages half the array, which is exactly linear search. So the degenerate tree is not merely bad in the worst case; it is bad on average by the same factor, and no amount of lucky querying rescues it.

A random tree’s mean depth is about $1.39 \log_2 n$, against a height of about $3 \log_2 n$. The gap between those two is larger than for the balanced tree, and it is where random trees get their reputation for being good enough: most lookups are near the mean depth and only a few pay the height.

This is the average-versus-tail distinction inside a data structure. A random tree’s average lookup is within 40% of optimal, and its worst is three times optimal, and which of those matters depends on whether the goal is total throughput or a bound on a single request.

What the site measures and what it does not #

The site builds unbalanced trees and measures their shape. It does not implement a balanced tree, and that is a real gap rather than an oversight worth hiding.

What the measurement establishes: that the unbalanced tree degenerates completely on sorted input, that the degeneration is exactly maximal, and that shuffling restores logarithmic height. Those are the claims the essay makes and each fails the build if it stops being true.

What it does not establish: the cost of rebalancing. The figures above quantify the problem precisely and quantify the solution only by reference to the ideal height, which a real red-black tree does not achieve either — it guarantees height at most $2\log_2(n+1)$, roughly twice the ideal, in exchange for $O(1)$ amortised rotations per insertion.

Measuring that trade properly would need a second implementation and a count of rotations alongside comparisons, which is the same shape of two-quantity measurement the sorting field uses. It is a natural thing for a later phase to add.

The other structures with the same disease #

Sorted input is bad for more than trees, and the pattern is worth recognising.

Hash tables with a poor hash. If the hash of consecutive integers is consecutive — which it is for the identity hash many implementations use for integer keys — then sequential keys land in adjacent slots, and under linear probing they form one long cluster. The measured probe count degrades badly, for the same reason: the input’s structure is being passed straight through to the structure’s layout.

Quicksort with a deterministic pivot. Covered in its own essay; sorted input produces maximally unbalanced partitions and quadratic behaviour.

Skip lists and treaps avoid it by construction, because they randomise internally rather than depending on the input’s order. That is the third fix alongside rebalancing and shuffling the input, and it is the one that requires the least discipline from the caller.

The common thread: a structure that derives its shape from the order of its input has a worst case, and the worst case is usually “sorted”. Any structure claiming a bound without saying which of the three fixes it uses is worth checking.

What a lookup actually costs #

The height is a count of edges, and a lookup follows them. What that costs on a machine is a separate question, and for trees the answer is worse than the count suggests.

Each edge is a pointer dereference to a node that the allocator placed wherever it had room. Consecutive nodes on a root-to-leaf path are almost never adjacent in memory, so a tree walk is close to the worst access pattern there is: a chain of dependent loads, each one a potential cache miss, and each one unable to start until the previous finished. The hardware cannot prefetch it, because it does not know the next address until the current load returns.

So a lookup in a tree of height 13 is about thirteen serialised misses, and a binary search in a sorted array of the same size is about thirteen misses too — but the array version needs no pointers, no allocation, and no per-node overhead, and its last few probes land in one cache line.

This is why B-trees exist. A B-tree node holds many keys, so one cache line or one disk block fetched gives many comparisons’ worth of progress, and the height drops by the branching factor’s logarithm. The structure is a direct response to the cost of a miss versus the cost of a comparison, and it is a good example of a data structure designed around the memory hierarchy rather than around an operation count.

The gap between the two heights is a function of $n$, and two more sizes say which way it runs.

What the measurement adds #

The claim “an unbalanced BST degenerates on sorted input” is standard and is usually accompanied by a small drawn example. What the measurement adds is the exactness.

The height is $n-1$, not “much worse than $\log n$”. The build cost is $\frac{n(n-1)}{2}$, the same as selection sort, not “quadratic-ish”. The shuffled tree’s height is about $3\log_2 n$, not “logarithmic”. Each of those is a number that can be checked on every build, and each of them fails loudly if the implementation changes.

The exactness also disciplines the essay. It is tempting to write that a balanced tree is “much faster” than an unbalanced one, and the honest version is that it is a factor of two or three faster on random input and unboundedly faster on sorted input, which are different claims with different consequences for whether one is worth using.