Two implementations build Huffman codes from the same next-hop frequencies and get different code lengths; is one wrong?

## Where the freedom comes from The construction says *take the two lowest-weight trees*. It does not say what to do when three trees weigh the same, or when a freshly created internal node weighs exactly as much as a leaf still in the pool. Both situations are common — merged weights are sums of the inputs, so collisions are the rule rather than the exception on tidy frequency tables. Every such tie is a genuine fork in the algorithm. There is a second, more superficial freedom: at each internal node, which child gets edge label `0`. Flipping labels changes every code word below that node and changes no length, so it cannot affect the cost at all. ## A worked case where the lengths really differ Next-hop shares 0.4, 0.2, 0.2, 0.1, 0.1. First merge is forced: the two 0.1s join into a 0.2. The pool is now `{0.4, 0.2, 0.2, 0.2}`, with three tied trees and a fork. - **Take the two original 0.2 leaves.** The pool becomes `{0.4, 0.2(merged pair), 0.4}`; joining 0.2 with a 0.4 and then the last two gives code lengths **2, 2, 2, 3, 3**. - **Take the merged 0.2 and one original 0.2.** Keep choosing so the growing tree absorbs one symbol per step, and you get a maximally lopsided tree with lengths **1, 2, 3, 4, 4**. Check the cost of each: | Length vector | Expected length | |---|---| | 2, 2, 2, 3, 3 | `0.4x2 + 0.2x2 + 0.2x2 + 0.1x3 + 0.1x3 = 2.2` | | 1, 2, 3, 4, 4 | `0.4x1 + 0.2x2 + 0.2x3 + 0.1x4 + 0.1x4 = 2.2` | Identical, to the bit. The codes look nothing alike — one is nearly balanced, the other a chain — and they compress exactly as well. ## Why the expected length is nevertheless unique Every tree the construction can produce is **optimal** for that frequency table: the greedy step is justified by an exchange argument that holds regardless of which of several equally light trees is picked. Optimality fixes the *value* of the expected length, not the structure that achieves it. So the set of Huffman codes for a distribution is generally large, and the function it minimises has one value. A practical consequence often missed: the two vectors differ in **maximum code length** (3 versus 4). When an implementation needs bounded code words — to use fixed-width decode tables, for instance — tie-breaking is one of the levers that affects the depth it gets, which is why some implementations deliberately prefer older or lighter subtrees on ties. ## When the non-determinism becomes a bug It depends entirely on how the decoder learns the table: - **The table ships with the data.** No problem at all. Whatever the encoder built is what the decoder uses, and tie-breaks are invisible. - **Both sides rebuild from a shared frequency list.** Now the tie-break rule is part of the wire contract. Two implementations, or two versions of one implementation, that break ties differently produce different tables from the same input and mis-decode each other's output — silently, because the wrong prefix-free table still parses the bits. - **Reproducible output is required.** If the same input must produce byte-identical compressed output across builds, ties must be broken by a total, stable rule such as `(weight, then earliest symbol index)`, and the rule must be documented rather than inherited from a data structure's ordering. The common practical answer is to sidestep the whole question: build whatever tree you like, then derive a **canonical code from the lengths** and ship the lengths. Both sides then agree on code words without agreeing on a merge order. ## The interview answer in one breath No, neither is wrong; ties make the tree non-unique while optimality makes the expected length unique; the only thing that must be pinned down is determinism, and only when both endpoints build the table independently.