Why is the optimal Huffman tree for an alphabet where one symbol is 90% of the stream unbalanced?

## The objective function, stated exactly Every question about Huffman tree shape resolves once you write down what is being minimized. For a code tree T over symbols with frequencies (or counts) w(s) and depths d(s), the cost is the **weighted path length**: > WPL(T) = sum over symbols s of w(s) times d(s) Because a symbol's depth equals its codeword length in bits, WPL with normalized frequencies is exactly the average bits per symbol the encoder will emit. Depth is not a structural nicety here — it is a **price paid once per occurrence**. That single observation explains the shape completely: put weight where the price is low. ## Working the skewed example A four-symbol stream where one symbol dominates — frequencies 0.90, 0.06, 0.03, 0.01 — is the sharpest illustration. Huffman repeatedly removes the two smallest weights and inserts their sum: | step | multiset before | merged | multiset after | |---|---|---|---| | 1 | 0.01, 0.03, 0.06, 0.90 | 0.01 + 0.03 = 0.04 | 0.04, 0.06, 0.90 | | 2 | 0.04, 0.06, 0.90 | 0.04 + 0.06 = 0.10 | 0.10, 0.90 | | 3 | 0.10, 0.90 | 0.10 + 0.90 = 1.00 | 1.00 (root) | Depths fall out of the merge order: the 0.90 symbol joined last, so it sits at depth 1; the 0.06 symbol at depth 2; the 0.03 and 0.01 symbols at depth 3. Codeword lengths 1, 2, 3, 3. - WPL = 0.90(1) + 0.06(2) + 0.03(3) + 0.01(3) = 0.90 + 0.12 + 0.09 + 0.03 = **1.14** - Balanced alternative, all depths 2: WPL = 2.00 A useful identity for checking your arithmetic: **WPL equals the sum of the weights of all internal nodes created during the build** — 0.04 + 0.10 + 1.00 = 1.14. It holds because a leaf's weight is counted once for every merge it participates in, which is exactly its depth. ## The wrong answer this question targets The reflex "trees should be balanced" comes from search structures, and it is right *there*: a lookup tree with n keys and uniform access wants height near log n because the cost model is worst-case depth per query. A code tree has a different cost model — expected depth, weighted. When weights are wildly unequal, minimizing the expectation demands imbalance. Saying "the optimal tree is unbalanced, so the algorithm must be broken" inverts the objective. Note the honest boundary of the claim: Huffman does not *prefer* imbalance, it is indifferent to it. Give it four equally frequent symbols and it produces a perfectly balanced tree with 2-bit codes everywhere — identical to the fixed-width code, WPL 2.00. Uniform frequencies are the case where the fixed-width code is already optimal, and Huffman rediscovers it. Skew is what creates the gap, and the more extreme the skew, the wider it grows. ## Directions that are easy to get backwards **Minimizing the average says nothing about the maximum.** A pathological weight distribution — counts following a Fibonacci-like pattern, where each weight exceeds the sum of all smaller ones — produces a fully degenerate chain in which the rarest symbol sits at depth n-1. The average stays excellent; one symbol's codeword becomes enormous. This is not a bug, it is the objective working as specified. That consequence matters in practice, which is why real formats bound it. Compressed-format designers made different calls on the same tension: DEFLATE-based archivers cap a code length at 15 bits and JPEG's baseline entropy coding at 16, so both must use a **length-limited** variant (the package-merge algorithm is the standard one) that accepts a slightly worse WPL in exchange for a hard ceiling on decoder table size. The plain greedy construction offers no such ceiling. **A one-bit symbol is the floor, not a target.** No prefix-free code can give any symbol fewer than one bit, so a symbol at 90% still costs 0.90 bits per symbol of stream. That is why per-symbol coding saturates on extremely skewed inputs and why formats that need to go further group symbols or code runs before applying a per-symbol code at all. **Small alphabets limit the win.** With two symbols the tree has exactly one shape: both leaves at depth 1, one bit each, no matter how lopsided the frequencies. The savings in the four-symbol example come from having enough symbols that depth can actually vary. ## What to say out loud Name the objective (weighted path length), trace the merges, produce the two numbers, and close with the contrast: balanced is right when every access is equally likely and you are bounding the worst case; weighted-optimal is right when accesses are skewed and you are minimizing the expected case. On uniform input the two answers coincide, which is the cleanest way to show you understand why they differ.