How does Huffman coding build a code tree from a table of next-hop identifier frequencies?

middlemust knowfreq 65%

answer

frequencies in, code tree out
always merge the two smallest
n symbols means n-1 merges
each merge adds a bit below it
depth of leaf is code length

basics

~20 s

Huffman coding repeatedly removes the two lowest-frequency trees and joins them under a new node weighted by their sum, until one tree remains. Each symbol's code is its root-to-leaf path, so rare symbols sink deepest and frequent ones stay shallow.

solid answer

~50 s

Start with one single-node tree per symbol, weighted by its frequency. Repeatedly pull the two lowest-weight trees out of the pool, join them under a new internal node whose weight is the sum, and put that back. After n-1 merges one tree is left; label each node's two outgoing edges 0 and 1, and a symbol's code is the path from the root to its leaf. The greedy step works because every merge adds exactly one bit to every symbol underneath it, so you want the least traffic sitting under the most merges. With five next-hop identifiers at shares 40/20/20/10/10, the code lengths come out 2, 2, 2, 3, 3 for an expected 2.2 bits per symbol, against 3 bits for a fixed-width code. Cost is O(n log n) in the alphabet size with a priority queue.

Start with one single-node tree per symbol, weighted by its frequency. Repeatedly pull the **two lowest-weight** trees out of the pool, join them under a new internal node whose weight is the sum, and put that back. After `n-1` merges one tree is left; label each node's two outgoing edges `0` and `1`, and a symbol's code is the path from the root to its leaf. The greedy step works because every merge adds exactly one bit to *every* symbol underneath it, so you want the least traffic sitting under the most merges. With five next-hop identifiers at shares 40/20/20/10/10, the code lengths come out 2, 2, 2, 3, 3 for an expected 2.2 bits per symbol, against 3 bits for a fixed-width code. Cost is `O(n log n)` in the alphabet size with a priority queue.

code

pseudocode · 18 lines

pseudocode

pool = empty priority queue ordered by weight
for each symbol s:
    pool.insert(leaf(s), weight = frequency[s])

while pool.size > 1:
    a = pool.remove_lowest()
    b = pool.remove_lowest()
    pool.insert(node(left = a, right = b), weight = a.weight + b.weight)

root = pool.remove_lowest()
assign_codes(root, prefix = "")

assign_codes(node, prefix):
    if node is a leaf:
        code[node.symbol] = prefix
    else:
        assign_codes(node.left,  prefix + "0")
        assign_codes(node.right, prefix + "1")

go deeper

for a junior

Remember the shape of the result: common symbols get short bit strings, rare ones get long bit strings, and the lengths come from a tree built out of frequencies rather than from the alphabet size.

for a middle

Be able to run the merge on a five-symbol frequency list at a whiteboard, read the code lengths off the depths, and compute the expected bits per symbol as a weighted sum. Say why the two smallest weights are the ones joined.

for a senior

Explain the cost model behind the greedy step — a merge charges the summed weight of what it pushes down — and know the practical consequences: an O(n log n) build over the alphabet, a first pass to collect frequencies, and long code words on skewed tables.

for a principal

Frame it as a build-time versus stream-time trade: the frequency pass and the tree build are paid per table, the code lengths are paid per symbol forever, and the alphabet you choose to count over decides how much redundancy the code can even see.

What a Huffman code is

A symbol code gives every symbol of an alphabet its own bit string, and the encoder emits those strings back to back with nothing between them. A fixed-width code spends the same number of bits on every symbol: five next-hop identifiers need 3 bits each, whether one of them carries 90% of the traffic or all five are equally likely. Huffman coding drops the fixed width. It takes a frequency or probability per symbol and produces a binary tree whose leaves are the symbols; reading one edge label per level from the root to a leaf gives that symbol's code word, and the code word's length is the leaf's depth. Frequent symbols end up shallow and cheap, rare ones deep and expensive, and the expected cost per symbol falls.

The greedy merge, step by step

Put every symbol into a pool as a one-node tree whose weight is its frequency.
Remove the two lowest-weight trees from the pool.
Join them as the two children of a new internal node whose weight is the sum of theirs.
Put that new tree back into the pool, and repeat from step 2 until a single tree remains.
Label the two edges leaving every internal node 0 and 1 (either way round), and read off each leaf's path.

An alphabet of n symbols takes exactly n-1 merges, because each merge reduces the pool size by one. The whole construction is O(n log n) when the pool is a priority queue keyed on weight; if the frequencies arrive already sorted, a two-queue variant — one queue of leaves, one of newly created internal nodes, both consumed in non-decreasing weight order — runs in linear time.

Why merging the rarest two is the right greedy step

The key observation is about what a merge costs. Putting a tree one level lower adds one bit to every symbol in it, and that bit is paid once per occurrence of those symbols. So the total price of a merge is the summed weight of the two trees joined. Merging the two lowest weights is therefore the cheapest available move at every step.

The optimality argument builds on an exchange: in some optimal tree, the two least frequent symbols can be made siblings at the deepest level, because swapping a deeper leaf with a more frequent shallower one never increases the expected length. Once they are siblings, they behave exactly like a single combined symbol of their summed weight, which is precisely the smaller problem the next merge step solves. Induction on that reduction gives the result: no other assignment of integer-length code words beats Huffman's expected length for that frequency table.

A worked five-symbol table

A router encodes next-hop identifiers whose traffic shares are wildly uneven:

Next hop	Share	Code length	One valid code
N1	0.40	2	`00`
N2	0.20	2	`01`
N3	0.20	2	`10`
N4	0.10	3	`110`
N5	0.10	3	`111`

The merge order is: N4+N5 first (weight 0.20), then two of the three weight-0.20 trees, and so on until one tree covers everything. The expected length is 0.4x2 + 0.2x2 + 0.2x2 + 0.1x3 + 0.1x3 = 2.2 bits per symbol. The Shannon entropy of that distribution is about 2.12 bits, and a fixed-width code over five symbols costs 3 bits. So the code recovers most of the available saving — roughly 27% off the fixed-width stream — and leaves about 0.08 bits per symbol on the table.

What the construction does not do

It needs the frequencies up front, which usually means either a first pass over the data or a table agreed in advance.
It is a per-symbol code: it sees the frequency of each identifier and nothing else, so a stream where the same next hop repeats in long runs looks no different to it than a shuffled one.
It never emits a fraction of a bit, so its per-symbol cost cannot fall below one bit no matter how predictable the source is.
Code words can be long — up to n-1 bits for n symbols in the worst, heavily skewed case — which implementations usually cap by flattening the frequencies slightly.

Those boundaries are exactly where the other lossless families start.

## What a Huffman code is A **symbol code** gives every symbol of an alphabet its own bit string, and the encoder emits those strings back to back with nothing between them. A fixed-width code spends the same number of bits on every symbol: five next-hop identifiers need 3 bits each, whether one of them carries 90% of the traffic or all five are equally likely. Huffman coding drops the fixed width. It takes a **frequency or probability per symbol** and produces a binary tree whose leaves are the symbols; reading one edge label per level from the root to a leaf gives that symbol's code word, and the code word's **length is the leaf's depth**. Frequent symbols end up shallow and cheap, rare ones deep and expensive, and the expected cost per symbol falls. ## The greedy merge, step by step 1. Put every symbol into a pool as a one-node tree whose weight is its frequency. 2. Remove the **two lowest-weight** trees from the pool. 3. Join them as the two children of a new internal node whose weight is the sum of theirs. 4. Put that new tree back into the pool, and repeat from step 2 until a single tree remains. 5. Label the two edges leaving every internal node `0` and `1` (either way round), and read off each leaf's path. An alphabet of `n` symbols takes exactly `n-1` merges, because each merge reduces the pool size by one. The whole construction is `O(n log n)` when the pool is a priority queue keyed on weight; if the frequencies arrive already sorted, a two-queue variant — one queue of leaves, one of newly created internal nodes, both consumed in non-decreasing weight order — runs in linear time. ## Why merging the rarest two is the right greedy step The key observation is about what a merge costs. Putting a tree one level lower adds **one bit to every symbol in it**, and that bit is paid once per occurrence of those symbols. So the total price of a merge is the summed weight of the two trees joined. Merging the two lowest weights is therefore the cheapest available move at every step. The optimality argument builds on an exchange: in *some* optimal tree, the two least frequent symbols can be made siblings at the deepest level, because swapping a deeper leaf with a more frequent shallower one never increases the expected length. Once they are siblings, they behave exactly like a single combined symbol of their summed weight, which is precisely the smaller problem the next merge step solves. Induction on that reduction gives the result: **no other assignment of integer-length code words beats Huffman's expected length for that frequency table.** ## A worked five-symbol table A router encodes next-hop identifiers whose traffic shares are wildly uneven: | Next hop | Share | Code length | One valid code | |---|---|---|---| | N1 | 0.40 | 2 | `00` | | N2 | 0.20 | 2 | `01` | | N3 | 0.20 | 2 | `10` | | N4 | 0.10 | 3 | `110` | | N5 | 0.10 | 3 | `111` | The merge order is: N4+N5 first (weight 0.20), then two of the three weight-0.20 trees, and so on until one tree covers everything. The expected length is `0.4x2 + 0.2x2 + 0.2x2 + 0.1x3 + 0.1x3 = 2.2` bits per symbol. The Shannon entropy of that distribution is about **2.12 bits**, and a fixed-width code over five symbols costs **3 bits**. So the code recovers most of the available saving — roughly 27% off the fixed-width stream — and leaves about 0.08 bits per symbol on the table. ## What the construction does not do - It needs the **frequencies up front**, which usually means either a first pass over the data or a table agreed in advance. - It is a **per-symbol** code: it sees the frequency of each identifier and nothing else, so a stream where the same next hop repeats in long runs looks no different to it than a shuffled one. - It never emits a fraction of a bit, so its per-symbol cost cannot fall below one bit no matter how predictable the source is. - Code words can be long — up to `n-1` bits for `n` symbols in the worst, heavily skewed case — which implementations usually cap by flattening the frequencies slightly. Those boundaries are exactly where the other lossless families start.

How many merges does the construction perform, and what does that cost overall?
Exactly `n-1` merges for `n` symbols, since each one removes two trees from the pool and returns one. With a priority queue that is `O(n log n)` in the alphabet size. If the frequencies are already sorted, the two-queue variant — one queue of leaves, one of internal nodes, each consumed in weight order — makes it linear, because no comparison-based ordering is needed any more.
What happens if two symbols have exactly equal frequencies?
Either may be picked as the lower of the two, so the construction is not deterministic unless a tie-break rule is fixed. Different tie-breaks can produce genuinely different code lengths, but every resulting tree has the same expected length, since all of them are optimal for that frequency table.
Can a Huffman code word ever be longer than a fixed-width code word?
Yes, for rare symbols. With `n` symbols, a maximally skewed frequency table drives the deepest code word to `n-1` bits, far beyond the `ceil(log2 n)` a fixed-width code would spend. That is a good trade, because those long words are paid on almost no traffic, but implementations that need bounded word lengths flatten the smallest frequencies before building.

Think of a building where every corridor forks in two. You put the busiest office one turn from the entrance and the storeroom nobody visits five turns away, because every extra turn is paid on every trip to that room.

saying these in an interview costs you the question

Merges the two most frequent symbols first
Thinks the code lengths come from sorting alone, with no tree
Believes a Huffman code always reaches the entropy
Assumes each symbol's code is its rank written in binary
Cannot say why a deeper leaf costs more bits
Thinks the construction needs the data, not just the frequencies

How does Huffman coding build a code tree from a table of next-hop identifier frequencies?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

What a Huffman code is

The greedy merge, step by step

Why merging the rarest two is the right greedy step

A worked five-symbol table

What the construction does not do

▾common follow-ups3 questions

▾analogy~20 s

▾red flags6 flags

What a Huffman code is

The greedy merge, step by step

Why merging the rarest two is the right greedy step

A worked five-symbol table

What the construction does not do

answer

go deeper