Algorithms & Data Structures
the bound is a claim, and it is checkable
Structures

The tree that is a list

A binary search tree gives logarithmic lookup. Build one from 128 keys in sorted order and it has height 127 — every node has one child, and a lookup is a linear scan. The failure is not gradual and it happens on the input people try first, which makes "O(log n) lookup" a claim about the insertion order rather than about the structure.
15 min read 6 figures Measured, not assertedThe figure is the run

A binary search tree supports lookup, insertion and deletion in O(log⁡n)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 same 63 keys, inserted in two ordersBoth trees hold the keys 0 to 62. On the left they arrived in order, and the tree has height 62 — every node has one child, and a lookup costs a linear scan. On the right the same keys arrived shuffled, giving height 10 against an ideal of 5. Both figures are truncated at depth 16 because the left one does not fit. The logarithmic lookup a binary search tree is chosen for is a property of the insertion order, not of the structure.sorted insertion — height 62shuffled insertion — height 10truncated at depth 1663 keys, identical set, different arrival order62 deep against 10
Fig. 1 The same 63 keys inserted in two orders. On the left they arrived sorted and the tree has height 62 — one child per node, all the way down. On the right the identical set arrived shuffled, giving height 10 against an ideal of 5. Both are binary search trees. Both are correct. One of them is a list.

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 nn sorted keys the height is exactly n−1n - 1: not 2log⁡n2\log n, not n\sqrt{n}, but the theoretical maximum for a tree with nn nodes. Every single insertion after the first descends the entire existing structure. The total cost of building the tree is n(n−1)2\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 nn sorted keys to have height exactly n−1n-1, because “worse than logarithmic” would be satisfied by a tree of height 3log⁡n3\log n, and the claim being made is much stronger than that.

It also requires the shuffled tree to be genuinely logarithmic — height under 3log⁡2n3 \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. A tree built from keys that are mostly ascending with occasional dips has height proportional to the length of the longest ascending run, which for realistic data is a large fraction of nn.

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:

insertion order height ideal height build comparisons
sorted 127 7 8,128
shuffled 13 7 778

The ideal is ⌊log⁡2128⌋=7\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.31ln⁡n4.31 \ln n, or roughly 3log⁡2n3 \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=128n = 128 and grows: at n=1,024n = 1{,}024 it would be about 50, and at n=106n = 10^6 about 25,000.

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\log n regardless of insertion order.

Measured against the two cases above, balancing buys:

  • against the sorted case, a factor of about n/log⁡nn / \log n — 18 at n=128n = 128, and unbounded as nn 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.

The same 31 keys, inserted in two ordersBoth trees hold the keys 0 to 30. On the left they arrived in order, and the tree has height 30 — every node has one child, and a lookup costs a linear scan. On the right the same keys arrived shuffled, giving height 10 against an ideal of 4. Both figures are truncated at depth 16 because the left one does not fit. The logarithmic lookup a binary search tree is chosen for is a property of the insertion order, not of the structure.sorted insertion — height 30shuffled insertion — height 10truncated at depth 1631 keys, identical set, different arrival order30 deep against 10
Fig. 2 The same comparison at a smaller size, where the individual nodes are legible. The sorted tree’s diagonal is not an artefact of the drawing — the layout places a node’s horizontal position by its rank and its vertical position by its depth, so a chain of single children genuinely goes down and across.

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 nn sorted keys has height n−1n-1 and mean depth n−12\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.39log⁡2n1.39 \log_2 n, against a height of about 3log⁡2n3 \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 2log⁡2(n+1)2\log_2(n+1), roughly twice the ideal, in exchange for O(1)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 same 127 keys, inserted in two ordersBoth trees hold the keys 0 to 126. On the left they arrived in order, and the tree has height 126 — every node has one child, and a lookup costs a linear scan. On the right the same keys arrived shuffled, giving height 12 against an ideal of 6. Both figures are truncated at depth 16 because the left one does not fit. The logarithmic lookup a binary search tree is chosen for is a property of the insertion order, not of the structure.sorted insertion — height 126shuffled insertion — height 12truncated at depth 16127 keys, identical set, different arrival order126 deep against 12
Fig. 3 The degeneration at twice the size, truncated at depth 16 because the sorted tree does not fit on a page at any scale. The truncation is itself the point: a structure whose picture cannot be drawn is a structure whose lookup cost cannot be drawn either.

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 randomising the pivot buys, n = 512For each pivot rule: the range of comparison counts over 400 random inputs (the bar), and the count on an already sorted array (the marker). Taking the first element as pivot costs 130,816 comparisons on sorted input — 26 times its random-input mean, and the quadratic behaviour the algorithm is supposed to avoid. Choosing the pivot at random costs 5,490 on the same input. Randomisation does not make the bad case impossible; it makes it independent of the input, so an adversary who knows the data cannot choose it.first-element pivot130,816 on sortedmedian of three5088 meanrandom pivot4937 meanblue bar: range over 400 random inputs · marker: the already-sorted inputn = 512a bad case that cannot be chosen is a different kind of bad case
Fig. 4 The same disease in the sorting field. Quicksort with a first-element pivot costs 130,816 comparisons on an already sorted array of 512 — 24 times its mean on random input. Randomising the pivot removes the input’s ability to choose the bad case, which is exactly what balancing does for a tree.

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.

Where each algorithm looks, and whenEvery array access from one run of each algorithm on 256 random elements: time along the horizontal axis, array index up the vertical. Heapsort makes 15% of its accesses to the next element or the same one; Merge sort makes 49%. That difference is invisible in the comparison count and is most of what the machine feels.Heapsort15% sequential · 14,044 accesses2560Merge sort49% sequential · 7,540 accesses2560time (accesses, left to right) · index (bottom to top)one run each, n = 256every access plotted
Fig. 5 The access pattern a tree walk resembles, from the closest thing on this site. Heapsort’s trace is a scatter of dependent jumps — a node to its child at twice the index — and it is the pattern that makes heapsort’s modelled miss count 3.7 times merge sort’s on 1.9 times the comparisons. A pointer-chasing tree walk is the same shape with worse locality.

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−1n-1, not “much worse than log⁡n\log n”. The build cost is n(n−1)2\frac{n(n-1)}{2}, the same as selection sort, not “quadratic-ish”. The shuffled tree’s height is about 3log⁡2n3\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.

The cost of each of 512 appendsOne spike per append, on a logarithmic vertical axis. Almost every append costs one unit. 9 of them cost the entire current size, because the array had to be copied, and the largest cost 257 — more than half of all the appends put together would suggest. The mean over the whole sequence is 2.00, which is the amortised cost, and it is a true statement about the sequence and a false one about any append in it.110100257amortised 2.000256512append numbercost of that append (log scale)growth factor 2, cost = 1 write + a copy of the array when it resizes9 resizes in 512 appends
Fig. 6 A structure whose bound survives any input order, for contrast. A dynamic array’s amortised append cost does not depend on what is being appended or in what sequence — there is no adversarial input, because the structure’s shape is a function of its size alone. That is a rarer property than it sounds.

Where this goes next

110100257amortised 2.000256512append numbercost of that append (log scale)growth factor 2, cost = 1 write + a copy of the array when it resizes9 resizes in 512 appends What amortised means Appending to a dynamic array is O(1) amortised. It is also, on 512 appends, an operation that costs one unit 503 times and 257 units once. The amortised bound is a true statement about the sequence and a false one about any append in it, and the picture that shows why is a sawtooth nobody draws. first-element pivot130,816 on sortedmedian of three5088 meanrandom pivot4937 meanblue bar: range over 400 random inputs · marker: the already-sorted inputn = 512a bad case that cannot be chosen is a different kind of bad case What randomising the pivot buys Quicksort taking the first element as its pivot costs 130,816 comparisons on an already sorted array of 512 — 27 times its cost on random data, and exactly the quadratic behaviour the algorithm exists to avoid. Randomising the pivot costs 5,490 on the same input. Randomisation does not make the bad case impossible; it makes it unchoosable. comparisons (bar length is log-scaled)sorting, floor43,250sorting, merge sort43,976searching, floor13searching, binary13searching, linear4,096green outline: a proved floor · blue: a measured run3,327× between the two floors The floor moves when the question does Sorting 4,096 elements needs at least 43,250 comparisons. Finding one element among the same 4,096, already sorted, needs at least 13. The difference is a factor of 3,300 and it comes entirely from how many different answers the algorithm has to be able to give. A lower bound is a property of the question, not of any algorithm.