Why must a Huffman code be prefix-free, and what breaks in decoding without it?
answer
- Where does one codeword stop?
- Symbols live only at leaves
- Decoder walks down, emits, restarts
- No codeword starts another codeword
- Codes 0, 01, 1 decode two ways
basics
~20 sPrefix-free means no codeword is the beginning of another, so a decoder reading bits one at a time always knows exactly where a symbol ends. Without that property the same bit stream decodes several different ways.
solid answer
~50 sHuffman builds a binary tree in which symbols sit **only at leaves**, and a symbol's codeword is the root-to-leaf path, `0` for one child and `1` for the other. Because no leaf lies on the path to another leaf, no codeword can be a prefix of another. That is what makes the stream self-delimiting: the decoder walks down from the root bit by bit, emits a symbol the instant it lands on a leaf, and jumps back to the root. Take away the property and ambiguity appears immediately — with codewords `0`, `01` and `1`, the bits `01` are either the second symbol alone or the first followed by the third, and no amount of lookahead settles it. Prefix-freeness costs zero extra bits, which is why it beats spending bits on separators or on a length field per symbol.
go deeper
Recall the definition and be able to show the failure in one line: with codewords 0, 01 and 1, the bits 01 have two readings. Then say where symbols sit in the tree — leaves only.
Explain why leaf placement makes the property structural rather than something you verify afterwards, and walk a short bit stream down the tree out loud, emitting and restarting at the root.
Show you know the boundary between decodability and optimality, and raise the end-of-stream problem unprompted: padding bits decode into phantom symbols unless a count or a terminator symbol is carried.
Frame the choice as a format decision: prefix-free coding buys instantaneous decoding at zero bit cost, and the alternatives — length fields, separators, fixed width — all trade bits or decoder complexity for the same guarantee.
## Why boundaries are the real problem A compression scheme that gives frequent symbols short codewords and rare symbols long ones must solve a problem that fixed-width codes never have: **where does one codeword end and the next begin?** With a fixed 2-bit code over a four-symbol alphabet the answer is trivial — cut every two bits. Once lengths vary, the decoder is handed an undifferentiated run of bits and has to find the cut points itself. There are only three ways to give it those cut points: 1. **Fixed width** — no savings, which defeats the purpose. 2. **Explicit separators or per-symbol length fields** — you spend bits describing the encoding instead of the data, and on a skewed stream that overhead can swamp the savings. 3. **A prefix-free (also called prefix, or instantaneous) code** — the codeword set itself is arranged so the cut points are unambiguous. This is free. Huffman coding takes the third route. ## The definition, precisely A code is **prefix-free** when no codeword is a proper prefix of any other codeword. `{0, 10, 110, 111}` is prefix-free. `{0, 01, 1}` is not: `0` is a prefix of `01`. And that failure is not cosmetic — the bits `01` decode as the single symbol coded `01`, or as the symbol coded `0` followed by the symbol coded `1`. Two legal readings of the same bits means the encoding has lost information. Note what prefix-free does **not** mean. It does not mean all codewords are the same length — that is the thing we are trying to escape. It does not mean codewords are unique — uniqueness is necessary but nowhere near sufficient, as `{0, 01, 1}` shows. And it is not the only way to be uniquely decodable: a code can be decodable only after reading ahead an unbounded distance. Prefix-free codes are the ones decodable **instantaneously**, symbol by symbol, with no lookahead and no backtracking. ## The tree makes it automatic The elegance of the tree formulation is that prefix-freeness is not something you check afterwards; it is a structural consequence. Build a binary tree, label the edge to one child `0` and to the other `1`, and place each symbol at a distinct **leaf**. A codeword is the sequence of edge labels from root to that leaf. Codeword X is a prefix of codeword Y exactly when X's node lies on the path to Y's node — and a leaf, by definition, has nothing below it. So leaf placement alone guarantees the property. Consider a four-symbol stream in which one symbol dominates: frequencies 0.90, 0.06, 0.03, 0.01. Huffman produces a tree giving codewords `1`, `01`, `001`, `000`. Feed the decoder `1 1 001 1 01`, i.e. the bits `110011 01`: it reads `1`, lands on a leaf, emits the dominant symbol, restarts; reads `1`, emits again; reads `0`, `0`, `1`, lands on the depth-3 leaf, emits the rare symbol; and so on. At no point does it need to know how long the next codeword will be. ## The end of the stream is a separate problem Prefix-freeness fixes boundaries **between** symbols; it says nothing about where the stream stops. Compressed output usually ends mid-byte, and the padding bits at the tail are a perfectly valid path down the tree, so a naive decoder emits one or more phantom symbols. Real formats solve this by storing an explicit symbol count alongside the data, or by reserving one extra alphabet member as an end-of-stream marker and coding it like any other symbol. Expect this as a follow-up. ## Prefix-free is a constraint, not the optimization A final distinction worth having straight: prefix-freeness makes a code **decodable**, not **good**. Infinitely many prefix-free codes exist over any alphabet, most of them terrible — the fixed-width code is itself prefix-free. What Huffman's greedy construction adds is that among all prefix-free codes for a given frequency table, the tree it builds minimizes the total weighted codeword length. The two properties are independent, and interviewers probe whether a candidate has conflated them. One more fact for the curious: the code lengths achievable by *some* prefix-free binary code are exactly those satisfying the Kraft inequality, the sum of 2 raised to the power of minus each length being at most 1. Lengths 1, 2, 2, 2 fail it (0.5 + 0.25 + 0.25 + 0.25 = 1.25), which is why no prefix-free code assigns them — a fast sanity check when someone proposes a code-length table.
- Does being prefix-free make a code optimal?No. Prefix-freeness is a decodability constraint, and infinitely many prefix-free codes exist for any alphabet — the fixed-width code is one of them. Huffman's contribution is choosing, among all prefix-free codes for a given frequency table, the one that minimizes total weighted codeword length. A candidate who treats the two properties as the same thing has missed what the greedy construction is actually optimizing.
- How does the decoder know when the stream is finished?Prefix-freeness resolves boundaries between symbols but says nothing about the end. The tail padding bits form a valid path down the tree, so a naive decoder emits phantom symbols. Fix it either by storing an explicit symbol count in the header or by adding a dedicated end-of-stream member to the alphabet, giving it a frequency of one and coding it like any other symbol.
- Could a symbol ever be stored at an internal node?Not in a prefix-free code. An internal node lies on the path to every leaf beneath it, so its codeword would be a prefix of all of theirs, and the decoder could never tell whether to stop there or keep descending. Any construction that places symbols at internal nodes has abandoned instantaneous decoding and needs separators to work at all.
It is the reason no country's phone numbers start with the emergency number: once you have dialled that prefix, the exchange must be able to act without waiting to see if more digits are coming.
saying these in an interview costs you the question
- Suggests separating codewords with a delimiter bit pattern
- Thinks prefix-free means all codewords share one length
- Places symbols at internal nodes of the code tree
- Claims the decoder needs each codeword's length up front
- Assumes prefix-free automatically means the code is optimal