In step 1 you wrote down an answer: what -sorted would do to a tree.

The same library. The same 10,000 titles. Only the insertion order changes:

$ algo gen -n 10000 -seed 7 -o s10k.jsonl
$ algo gen -n 10000 -seed 7 -sorted -o s10k-sorted.jsonl
$ algo shape -shuffled s10k.jsonl -sorted s10k-sorted.jsonl

insert order        n   height     log2 n    cmps/lookup  lookup time
shuffled        10000       30       13.3           16.7      2.488ms
-sorted         10000    10000       13.3         5000.5    532.978ms
linear (L1)     10000        -          -          5000.5    117.418ms

both trees hold the same keys and both answer correctly.

A height of 10,000

Not 10,000 nodes — 10,000 levels. One per record.

Every new title is larger than everything before it, so it always goes right and always becomes a leaf at the very bottom. No node ever acquires a left child. What you built is this:

Babažėrė Tiči
   └── Babosakė
          └── Baboti
                 └── Babočudu
                        └── ... 9,996 more levels

That is a singly linked list. Lesson 3, with an unused left pointer in every node.

5000.5

Look at the bottom two numbers in the cmps/lookup column.

-sorted        5000.5
linear (L1)    5000.5

Not "about the same". Exactly the same number — (n+1)/2, the one lesson 1 measured for linear search. And it has to be: walking a list from the front until you find the key is a linear search, whatever you named the type.

Twelve lessons of work, two pointers per node, an in-order traversal — and you are back precisely where you started.

And worse than it looks

Compare the times rather than the comparisons:

-sorted        532.978ms
linear (L1)    117.418ms

The same comparison count, and 4.5× longer.

The linear scan walks a contiguous slice: the processor runs ahead, pulls several records at once and almost never waits for memory. The degenerate tree walks pointers between 88-byte nodes scattered across the heap, and each step is a separate access to an address it could not have predicted.

That is the same point transit made about memory layout in lesson 10 — except now it is in your own numbers.

A degenerate tree is not "as bad as linear search". It is worse than what you had in lesson 1.

And that is the third time the counter has missed something

Look at what just happened. Both rows read 5000.5 comparisons. The counter says exactly the same amount of work was done. The clock says 4.5× more.

lesson	what the counter could not see
4	memory — it reported zero where the heap was growing
6	itself: with the counter in the loop the crossover moved from n ≈ 6 to n ≈ 3
11	memory layout — the same 5000.5, two entirely different times

This is not a flaw in the counter. It measures comparisons, and here they genuinely are equal. But a comparison reached through pointers scattered across the heap and a comparison in a contiguous slice do not cost the same, and the instrument cannot see that difference in principle.

When two versions give the same number and you can still feel a difference, that is the sign you are measuring the wrong thing. Reach for the clock.

The third time, and again the other way

This is -sorted changing the answer for the third time, in a different direction each time:

lesson	what -sorted did
7	gave insertion sort its best case, O(n)
8	gave quicksort its worst case, O(n²)
11	gave the BST its worst case, O(n) instead of O(log n)

The same flag, the same data, three different outcomes. Data is not "good" or "bad" in itself — it suits a particular algorithm or it does not, and the only way to know which is to measure.

If in step 1 you guessed that sorted data would make the tree's job easier, that is an entirely natural guess. Sorted data sounds like order, and a tree holds order. But a tree produces order; it does not consume it. What it needs is for the keys to arrive out of order.

And it is still correct

The last line of the measurement says: both trees hold the same keys and both answer correctly.

The degenerate tree finds everything it should. Keys() still returns a sorted list. Min, Max and ranges all work. Not one correctness test fails.

That is what makes it dangerous. There is no error, no wrong answer, nothing to find in a log. There is only a program that is behaving correctly and running a hundred times slower than you think — until you measure the depth.

Which is why Height() is a method of its own.