Huffman coding shrinks data by assigning short codes to frequent symbols and long codes to rare ones. The codes are prefix-free — no code is a prefix of another — so a stream of bits can be decoded unambiguously without separators. It’s the entropy-coding stage of DEFLATE (gzip/zlib) and JPEG.

How It Works

1. Count frequencies — every symbol becomes a leaf weighted by how often it occurs.
2. Merge the two smallest — take the two least-frequent nodes and combine them into a parent whose weight is their sum.
3. Repeat — keep merging until a single tree remains. The two smallest are always chosen (greedy choice).
4. Assign codes — walk the tree, emitting 0 for left branches and 1 for right branches. Leaves that appear more often sit higher and get shorter codes.

Key Insight

The greedy choice is provably optimal: at each step, merging the two least-frequent symbols cannot hurt — any optimal tree can be rearranged so its two lowest-frequency leaves are siblings. Repeating this invariant all the way up produces a code with the minimum possible expected length for the given frequencies. This is the classic exchange argument in action.

Worked Example

The visualizer uses the canonical frequency table a:5, b:9, c:12, d:13, e:16, f:45:

1. Merge a(5) and b(9) → ab(14).
2. Merge c(12) and d(13) → cd(25).
3. Merge ab(14) and e(16) → abe(30).
4. Merge cd(25) and abe(30) → abcde(55).
5. Merge abcde(55) and f(45) → root abcdef(100).

Walking the tree assigns f → 0 and a 4-bit family to a/b/c/d/e. The heavier symbol f gets the shortest code, and the total bit cost is far below the 3 bits/symbol a fixed 6-symbol code would need.

Edge Cases & Pitfalls

• Single symbol: a one-leaf tree needs no bits — guard against emitting an empty code.
• Uniform frequencies: all codes end up nearly equal length; Huffman gains nothing over fixed-length encoding.
• Tie-breaking: equal frequencies can merge in any order — the tree may differ, but the total cost is identical.
• Decoding: without the frequency table (or canonicalization), the receiver can’t decode — real formats ship it separately.
• Two passes: encoding needs frequencies before codes exist, so you either scan twice or buffer.

Applications

• File compression — gzip, DEFLATE, ZIP, PNG
• Media — JPEG, MP3 entropy coding
• Data transmission — reducing bandwidth when symbol distributions are skewed

Practice Trajectory

1. Hand-merge the five-step tree above and confirm each chosen pair.
2. Walk the finished tree and write out the code for f and for a.
3. Compute total bits and compare with a fixed-length code of ceil(log2(6)) = 3 bits per symbol.
4. Redo the tree with f and e swapped — confirm the total stays the same.
5. State the exchange argument in your own words and explain why the two smallest must be siblings.