Five tasks.

---

1. Save the tree and reload it

You want to write the tree to a file and restore it later. The obvious way: save Keys() and, on load, call Put for each key in turn.

Build a 2,000-item tree, note its height, then rebuild it that way and measure the height again.

Then try a pre-order traversal — "me, left, right" — and rebuild from that.

original tree:           height 37
reloaded from in-order:  height 2000
reloaded from pre-order: height 37

Explain both numbers. Why does the pre-order traversal restore exactly the same shape while the in-order one destroys it?

And what does that say about what "saving a tree" means? What are you actually saving — a set, or a structure?

---

2. Delete

Add func (t *TreeIndex) Delete(title string, c *metrics.Counter) bool.

Three cases, and only the third is hard:

• the node is a leaf → cut it off;
• it has one child → lift the child into its place;
• it has two children → replace it with its successor (the smallest key in the right subtree), then remove the successor from where it was.

Delete 500 of 1,000 and check three things: Len() is 500, the deleted keys are gone, the rest are still found — and Keys() is still sorted. That last one is the real test: a wrong Delete usually leaves a tree that still finds things but is no longer ordered.

To finish: why the successor specifically? Why does the predecessor (the largest key in the left subtree) work equally well, and no other node does?

---

3. Is the pruning real

Write rangeNoPrune: a full traversal with a filter at the end. The result is the same; what matters is how many nodes were visited.

range t05000..t05009:    10 hits — pruned    28, full walk 10000
range t02000..t02999:  1000 hits — pruned  1016, full walk 10000
range t00000..t09999: 10000 hits — pruned 10000, full walk 10000

Explain the last line. Why does pruning gain nothing there — and why is that not a defect?

Then write down Range's cost in terms of two quantities: n and the number of hits k. Which one actually governs it?

---

4. Predecessor, successor and "the next 20"

Implement Successor(title string) (string, bool) — the smallest key larger than the one given.

Two cases: if the node has a right subtree the answer is in there (its minimum); if it does not, you have to climb, and your nodes have no parent pointer. Solve it without adding one (hint: remember the last left turn you took on the way down).

Then build "the next 20 after this one" and measure what it costs in nodes. Compare with what lesson 10 would have to do for the same question.

---

5. Where the tree loses to its own output

In step 5 the tree trailed the hash table by 12.8×, and in step 6 transit chose a sorted slice.

Measure a third option: take Keys(), get a sorted array of titles, and search it with lesson 6's BinarySearch.

Compare all three at n = 10,000: comparisons per lookup, time, memory. The array should beat the tree on both counts.

Answer in one sentence: if a sorted array wins on lookup and on memory, why did you build the tree at all? (The answer is in step 6 and it is one word.)