SICP Exercise 2.71

Question

Suppose we have a Huffman tree for an alphabet of $n$ symbols, and that the relative frequencies of the symbols are $1,2,4,\dots ,2^{n-1}$. Sketch the tree for $n=5$; for $n=10$. In such a tree (for general $n$) how many bits are required to encode the most frequent symbol? The least frequent symbol?

Answer

The trees are very unbalanced:

In the best-case scenario, you only need $1$ bit to encode a symbol. For the least frequent symbol, however we need $n-1$ bits.