The Dictionary Shelf

Part A: try every root

For keys with frequencies $4,2,6,3$, the best tree has key 2 (frequency 6) at the root, key 0 under it on the left with key 1 below that, and key 3 on the right. That costs $6·1+4·2+3·2+2·3=26$. Every other tree costs more, which the dynamic program below checks without listing them all.

Part B: popular is not the same as central

With frequencies $10,9,9,9$ the popular-root rule puts key 0 at the root and the other three in a chain to its right: $10+18+27+36=91$. A tree rooted at key 1 costs 74, so the rule pays $91/74\approx 1.23$ times as much. A root pushes everything on its side one level deeper, so it should split the weight, not just be heavy. With 4 keys the worst the rule can do is $5/4$: equal frequencies, where its tie-breaking builds a chain.

Part C: the interval dynamic program

Let $C(i,j)$ be the cost of the best tree on keys $i,\dots ,j-1$, and $W(i,j)$ their total frequency. If key $r$ is the root, both subtrees hang one level lower, and every key in the range pays one more comparison: $$C(i,j)=W(i,j)+{min}_{i\le r<j}(C(i,r)+C(r+1,j)),C(i,i)=0.$$ Fill the table by increasing range length and remember the best $r$ for each range. Then rebuild the tree from $(0,n)$ downward. That is $O(n^2)$ ranges with $O(n)$ choices each, $O(n^3)$ in all. Returning the tree, not just the number, makes the answer checkable: the grader rebuilds it, recomputes its cost and compares it with the optimum.

Three rules that sound reasonable fail the grader:

• The popular root fails as soon as frequencies are equal.
• The middle key ignores the frequencies.
• Splitting the total frequency evenly comes close, but not exactly: about 8% over the best on the grader's 40 random keys.

Going further

• Knuth's speed-up. The best roots are monotone: $\text{root}(i,j-1)\le \text{root}(i,j)\le \text{root}(i+1,j)$. Searching only that window makes the whole table $O(n^2)$; the grader uses it. The same idea (the quadrangle inequality) speeds up many interval DPs.
• Near-optimal in linear time. Choosing the root that splits the weight most evenly is within a small additive term of optimal (Mehlhorn), which is why part C's third rule is close.
• Without knowing the frequencies, splay trees are within a constant factor of the best static tree on every access sequence (Sleator and Tarjan's static optimality theorem). See Splay Trees.

References

1. D. E. Knuth. Optimum binary search trees. Acta Informatica 1, 1971.
2. K. Mehlhorn. Nearly optimal binary search trees. Acta Informatica 5, 1975.
3. D. D. Sleator, R. E. Tarjan. Self-adjusting binary search trees. Journal of the ACM 32(3), 1985.