## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 2.71

From Drewiki

## Problem

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

## Solution

The tree for *n*=5:

+ / \ 16 \ \ + / \ 8 \ \ + / \ 4 \ \ + / \ 2 1

The encodings for this tree are 0, 10, 110, 1110, and 1111.

The tree for *n*=10 is similar. For each such tree, 1 bit is required to encode the most frequent symbol (as 0), and *n*-1 bits are required to encode the least frequent symbol.