The same library, the same 10,000 questions, three structures:

$ algo tree -in s10k.jsonl
n = 10000 distinct titles

  tree height      30   (log2 n = 13.3)
  in order?        true

                      cmps/lookup     build cmps  lookup time
  tree                     16.703         157025      3.108ms
  hash (lesson 10)          1.310           7198      1.001ms
  linear (lesson 1)         5000.5              0        125ms

  build time: tree 4ms, hash 2.501ms

  keys in sorted order: tree yes (walk), hash no (must sort all 10000)

The tree loses to the hash table by 12.8× on the one question "is this title present". Building it costs 157,025 comparisons against 7,198 — twenty-two times more.

Say that plainly rather than stepping around it. If your program only ever needs exact-key lookup, the hash table is the right choice and a tree would be a mistake.

Where those 16.7 go

The height is 30 and log2(10000) is 13.3. The tree is more than twice as deep as an ideal one.

That is expected. No node is looking after the balance — the tree takes whatever shape insertion order gives it, and random order gives a lopsided one rather than a catastrophic one. Measured:

$ for n in 100 1000 10000 100000; do algo gen -n $n -seed 7; algo tree; done

        n   height   log2 n    cmps/lookup
      100       13      6.6          7.710
     1000       22     10.0         12.273
    10000       30     13.3         16.703
   100000       41     16.6         21.367

A hundredfold increase in n, from 1,000 to 100,000, moved the cost from 12.3 to 21.4 — less than double. That is what a logarithm is: it grows, and the growth dies away.

Divide the columns into each other and a steady multiple appears:

n	height ÷ log2 n	comparisons ÷ log2 n
100	1.97	1.17
1,000	2.20	1.23
10,000	2.26	1.26
100,000	2.47	1.29

Not 1.0, but not a growing quantity either. The tree is roughly twice as deep as ideal and stays that way — which is exactly what "O(log n) with a worse constant" means.

The hash table's column in the same table would have read 1.31 throughout, with no log n in it at all.

Memory: measure it, do not assume

A tree node carries two pointers where a chain entry carried one:

Item         56 bytes
entry (L10)  80 bytes  (key + record + 1 pointer)
node  (L11)  88 bytes  (key + record + 2 pointers)

Eight bytes per node — so the tree looks more expensive. Now add up the whole structure at n = 10,000:

hash: 10,000 × 80 B  +  16,384 buckets × 8 B  =  931,072 B
tree: 10,000 × 88 B                           =  880,000 B

In total the tree uses less. Because the hash table does not only pay for its entries — it pays for its bucket array too, and that array is precisely what buys it the short chains. At load factor 0.61 there are 8,925 empty buckets, and every one of them takes up room.

Per node the tree costs more; per structure it does not. Which way it lands depends on the load factor you chose in lesson 10.

The trade, in two lines

Hash table: 1.3 comparisons per question, and one question. Tree: 16.7 comparisons, and six questions.

The second column is not "the same thing, but slower". It is a different product.