How Does Huffman Coding Build an Optimal Prefix-Free Tree?

Huffman coding constructs an optimal prefix-free variable-length binary tree by using a greedy bottom-up algorithm driven by symbol frequencies. Starting with each symbol as a leaf node weighted by its frequency or probability, the algorithm repeatedly merges the two nodes with the smallest weights into a new parent node until only a single root node remains. Assigning binary digits to the left and right branches of this tree produces codewords that minimize the average code length while ensuring no codeword is a prefix of another.

Symbol Frequencies and Prefix-Free Codes

In classical data compression, a source emits symbols from an alphabet \(S = \{s_1, s_2, \dots, s_n\}\) with corresponding frequencies or probabilities \(p_1, p_2, \dots, p_n\). Fixed-length encodings assign \(\lceil \log_2 n \rceil\) bits to every symbol, which wastes space when some symbols occur much more frequently than others. Variable-length encodings assign shorter bit strings to frequent symbols and longer bit strings to rare symbols.

For a variable-length code to be uniquely decodable without delimiters, it must be prefix-free. A code is prefix-free if no codeword is the leading substring of any other codeword. This property maps directly to a binary tree where every encoded symbol resides at a leaf node, and internal nodes represent prefixes shared by their descendants.

The Greedy Bottom-Up Construction Algorithm

Huffman's algorithm builds the binary tree from the leaves up using a min-priority queue (typically implemented as a binary min-heap) keyed by node weight:

  1. Create a leaf node for each symbol \(s_i \in S\) with weight \(w_i = p_i\) (or its raw frequency count) and insert all \(n\) leaf nodes into the min-priority queue.
  2. While the priority queue contains more than one node:
    • Extract the two nodes \(u\) and \(v\) with the smallest weights.
    • Create a new internal node \(z\) whose weight is \(w_z = w_u + w_v\).
    • Set \(u\) and \(v\) as the left and right children of \(z\).
    • Insert \(z\) back into the priority queue.
  3. When only one node remains in the queue, that node is the root of the completed Huffman tree.

Because each merge reduces the number of nodes in the queue by one, the loop executes exactly \(n - 1\) times. Using a binary min-heap, each extraction and insertion takes \(O(\log n)\) time, giving the overall construction a time complexity of \(O(n \log n)\).

Assigning Binary Codewords

Once the tree is constructed, codewords are generated by traversing from the root to each leaf. A standard convention assigns a 0 bit when moving to a left child and a 1 bit when moving to a right child. The codeword for a symbol \(s_i\) is the sequence of bits along the path from the root to its leaf, and its length \(l_i\) equals the depth of that leaf.

Because symbols only appear at leaves, no path to a symbol can be a prefix of the path to another symbol. Consequently, a decoder can read an incoming bitstream one bit at a time, traversing the tree from the root until it reaches a leaf, outputting that symbol, and immediately resetting to the root for the next bit.

Why the Resulting Tree Is Optimal

The goal of Huffman coding is to minimize the expected codeword length:

\[L = \sum_{i=1}^{n} p_i l_i\]

Huffman coding achieves this minimum through two properties:

  • Greedy choice property: The two symbols with the lowest probabilities can always be placed at the maximum depth of an optimal tree as siblings. If they were not, swapping them with the deepest nodes would not increase—and could only decrease—the weighted path length \(L\).
  • Optimal substructure: Merging the two lowest-weight nodes \(u\) and \(v\) into a single node \(z\) with weight \(p_u + p_v\) reduces the problem to finding an optimal tree for \(n - 1\) symbols. The cost of the original tree equals the cost of the reduced tree plus \(p_u + p_v\).

By induction over the \(n - 1\) merges, the final binary tree is guaranteed to achieve the minimum possible expected codeword length among all prefix-free binary codes for the given symbol frequencies.