Two Huffman encoders build different codebooks from the same frequency table — is either one wrong?
answer
- The guarantee is about cost, not shape
- What happens when three weights tie?
- Which child gets bit 0?
- Equal totals, different per-symbol lengths
- Counts 1,1,2,2 give two optimal trees
basics
~20 sNot necessarily. Ties between equal weights during merging, and the free choice of which child gets bit 0, yield several distinct trees that all hit the same minimum weighted total, so the codebook has to travel with the compressed data.
solid answer
~50 sHuffman guarantees a **minimum** weighted path length, not a unique tree. Two freedoms create the divergence: when three or more items share the smallest weight the algorithm may take any two of them, and the assignment of `0` and `1` to a node's children is arbitrary. Counts 1, 1, 2, 2 make this concrete — one valid run gives codeword lengths 2, 2, 2, 2 and another gives 1, 2, 3, 3, and both total 12. So per-symbol lengths can genuinely differ while the cost is identical. Practically: ship the codebook, or the code lengths plus a canonical rule for deriving codes from them; never assume a decoder can rebuild the tree from frequencies; never assert exact compressed bytes in a test. And a single distinct symbol yields a lone leaf at depth 0 — a zero-bit codeword that hangs a decoder unless special-cased.
code
pseudocode · 11 lines// decode one symbol from the bit stream
node = root
while node is not a leaf:
b = next_bit(stream)
if b == 0:
node = left(node)
else:
node = right(node)
emit(symbol(node))
// single-symbol alphabet: root IS a leaf
// -> zero bits consumed, outer loop never advancesgo deeper
Know that the algorithm guarantees a minimum total cost rather than one specific tree, and that flipping which child means 0 already changes every codeword.
Explain both sources of freedom — ties among equal weights and arbitrary child labelling — and show two trees with equal totals but different per-symbol lengths. Be clear that a tie is broken only among minimum-weight items.
Bring the production consequences: the codebook or the code lengths must travel with the stream, tests assert round-trip fidelity rather than exact bytes, and the degenerate single-symbol input needs an explicit special case.
Own the reproducibility policy. Decide whether byte-identical output is a requirement — for signing, deduplication or cache keys — and if so pin a total order for tie-breaking and a canonical code assignment rather than relying on incidental container ordering.
## Two independent sources of freedom The greedy rule is "remove the two smallest weights, insert their sum." It is deterministic about *which weights* qualify only when the smallest two are unambiguous. It says nothing at all about: 1. **Ties.** When three or more items share the minimum weight — extremely common with small integer counts, and guaranteed once merged sums start colliding with original weights — any two of them are a legal choice. 2. **Child order.** Which child of an internal node gets `0` and which gets `1` is arbitrary. Flipping every node's children produces a completely different codebook with identical lengths. Both are genuine degrees of freedom in the algorithm, not implementation sloppiness. Huffman's guarantee is about the **value** of the objective, not the identity of the tree achieving it. ## A concrete pair of optimal trees Take four log-message categories with counts 1, 1, 2, 2 (call the rare ones r1, r2 and the common ones c1, c2). The first merge is forced: r1 + r2 = 2. Now the multiset is {2 (the new node), 2 (c1), 2 (c2)} — a three-way tie. **Choice A — merge c1 with c2:** that node weighs 4; the root joins it with the r-node. Every leaf lands at depth 2. Lengths 2, 2, 2, 2. Cost = 1(2) + 1(2) + 2(2) + 2(2) = **12**. **Choice B — merge the r-node with c1:** that node weighs 4, containing the r-node at depth 2 and c1 at depth 2 within the whole tree; the root joins it with c2, which lands at depth 1. Lengths: c2 gets 1 bit, c1 gets 2, r1 and r2 get 3 each. Cost = 2(1) + 2(2) + 1(3) + 1(3) = **12**. Same total, different length multisets — {2,2,2,2} versus {1,2,3,3}. Both are correct Huffman outputs. Verify either with the internal-node identity: A gives 2 + 4 + 6 = 12, B gives 2 + 4 + 6 = 12. The important sharpening: a tie must be broken **among the minimum-weight items only**. In the multiset {2, 2, 4}, merging 2 with 4 is not a tie-break, it is a violation of the rule, and it produces a strictly worse tree. Candidates who have absorbed "ties are arbitrary" sometimes over-generalize to "the order barely matters." ## Consequences that actually bite in production **The decoder cannot re-derive the tree from the data.** Since several optimal trees exist, the decoder must be handed the exact one. Formats do this in one of two ways: transmit the code lengths per symbol and reconstruct codes by a **canonical** rule (sort by length, then by symbol index, assign codes in increasing numeric order), or transmit a serialized tree. Canonical codes are the mainstream choice — they are compact, and they eliminate the child-order freedom by fiat, so encoder and decoder cannot disagree. **Byte-for-byte reproducibility is a property you must engineer.** Two builds of the same encoder with a different tie-break — a different container ordering, a different comparator for equal weights, a parallel build — produce different but equally valid output. Tests that assert exact compressed bytes will break for no real reason; assert round-trip fidelity and total compressed size instead. If exact reproducibility is a requirement (signing, deduplication, cache keys), pin a total order for tie-breaking: compare by weight, then by a stable symbol identifier, then by insertion sequence. **Tie-breaking policy has a real, if small, effect.** Preferring already-merged nodes over original leaves when weights tie tends to produce trees with a smaller maximum codeword length and equal total cost — useful when the format caps code length. So although any tie-break is optimal by weighted path length, they are not interchangeable by *shape*. ## The degenerate inputs **One distinct symbol.** The heap starts with a single item, the merge loop never executes, and the root is itself a leaf at depth 0 — a codeword of zero bits. A decoder that reads bits until it reaches a leaf never consumes a bit and never terminates; an encoder emits nothing and the output is empty regardless of length. Every real implementation special-cases this, typically by forcing a one-bit code and recording the symbol count in the header. It is a favourite interview follow-up because it is where the elegant tree formulation quietly breaks. **Two distinct symbols.** Exactly one tree shape exists: both leaves at depth 1, one bit each, no matter how lopsided the counts are. Per-symbol coding can offer nothing here. **Zero-frequency symbols.** Symbols with count 0 must be excluded from the build, not fed in as weight-0 leaves; including them consumes code space and lengthens real codewords for nothing. ## What a strong answer sounds like "Both are optimal — the algorithm fixes the cost, not the tree. Ties among equal weights and the arbitrary 0/1 child labelling both create valid variants, so the decoder needs the actual codebook or a canonical rule for deriving codes from lengths. And I would not assert exact bytes in tests, only round-trip equality and total size."
- How do formats avoid shipping a whole tree?They ship only the code length per symbol and rebuild codes by a canonical rule: group symbols by length, order them by a fixed symbol index, and assign numerically increasing codes, shifting left at each length boundary. Lengths are far cheaper to store than a serialized tree, and the rule removes the arbitrary child-order freedom entirely, so encoder and decoder cannot drift apart.
- If any tie-break is optimal, does the choice matter at all?Not for total cost, but it does change tree shape. Preferring already-merged nodes over original leaves when weights tie tends to produce a smaller maximum codeword length at the same weighted total, which matters when a format caps code length or when decoder table size is bounded by the longest codeword. It also matters for reproducibility: a pinned total order makes output byte-identical across runs.
- What breaks when the input contains exactly one distinct symbol?The merge loop never runs, so the root is the only leaf and its codeword has zero bits. The encoder emits an empty stream and a decoder that descends until it hits a leaf consumes no bits and never advances. Implementations special-case it, assigning a one-bit code and storing the symbol count in the header so the decoder knows how many to emit.
saying these in an interview costs you the question
- Insists Huffman output is unique for a given frequency table
- Assumes the decoder can rebuild the tree from frequencies alone
- Treats differing per-symbol lengths as proof of a bug
- Breaks a tie by merging a minimum weight with a larger one
- Asserts exact compressed bytes in a regression test
- Ignores the single-symbol input that yields a zero-length codeword