Huffman Decoding

Decoding requires the SAME code table the encoder used. Walk the tree bit-by-bit:

state = root
for each bit in compressed:
    state = state.left if bit == '0' else state.right
    if state.is_leaf():
        emit(state.symbol)
        state = root

Huffman codes are prefix codes (no code is a prefix of another). That's what makes decoding unambiguous: the moment you reach a leaf, you know the symbol — no lookahead needed.

Example: codes {a:0, b:10, c:11}. Decoding 01011:

0    -> root.left = leaf 'a' -> emit 'a', reset
1    -> root.right (internal)
0    -> internal.left = leaf 'b' -> emit 'b', reset
1    -> root.right (internal)
1    -> internal.right = leaf 'c' -> emit 'c', reset

Output: abc.

In real implementations (zlib, gzip), the decoder uses a lookup table instead of a tree walk for speed:

• Build a table of length 2^max_code_length
• For each entry, store (symbol, code_length) — the symbol whose code prefixes that table index
• Per byte input: look up 8 bits; advance by code_length; repeat

This costs more memory but eliminates per-bit branching, dramatically speeding up the decode loop. Modern decoders unroll further (zlib's lookup is two-tier).