Lesson 10 ended on a question your index could not answer: give me the library in alphabetical order. Bucket order meant nothing, and getting the alphabetical list cost a full sort of all 1,000 keys.

Here is the same question, asked of a tree:

$ algo gen -n 1000 -seed 3
$ algo alpha -n 6 -from Bam -to Bat
the first 6 titles, walked out of the tree:
  Bagogū Guže
  Bamežanė Pako
  Bamila
  Basėrūno
  Batalu
  Batėvovu Sūvi

1000 keys in order, 0 comparisons, 0s
min "Bagogū Guže", max "Žūčibužu Kėpo"

range [Bam .. Bat]: 3 titles, 11 nodes visited out of 1000
  Bamežanė Pako
  Bamila
  Basėrūno

The same six titles. The same library, the same seed.

But in lesson 10 they cost a full sort of 1,000 keys, and here they cost 0 comparisons. Not fewer; none.

Why zero

Because nothing needed sorting. The tree never held the keys in any other order.

The hash table destroyed the order — that was its job, and it is why the chains stayed short. The tree keeps the order in its shape: every node has smaller keys to its left and larger keys to its right. Walk it "left, me, right" and the keys come out ascending, because there was no other order in there to begin with.

No sort function was called. A structure was walked.

And everything else lesson 10 could not do

Remember that table? Here it is again, with a second column:

question	hash table	tree
is "Bamila" there?	1.3 comparisons	~16 comparisons
which is first alphabetically?	only by sorting everything	Min() — walk left
which start with "Ba"?	only by scanning everything	a range query
what are the 20 after "Bamila"?	not a concept it has	continue the walk
which book comes before this one?	not a concept it has	the predecessor
highest rating?	only by scanning everything	Max() — walk right

Look at the range query above: 11 nodes visited out of 1,000. The tree did not scan the library — it descended to the band and skipped the subtrees that could not contain an answer.

And look at the first row. The tree loses. 16 comparisons against 1.3 — twelve times worse at the one question a hash table is for.

That is neither a defeat nor a victory. It is the other side of the trade, and step 5 pays for it in exact numbers.

Guess before you read on

There is one more thing, and it is why this lesson will end unresolved.

In lesson 1 you built a -sorted flag. In lesson 7 it gave insertion sort its best case. In lesson 8 it gave quicksort its worst.

What will it do to a tree: make its job easier, or harder?

Write your answer down. Step 7 measures it.