Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 31 / 1 / e

A full binary tree has Kraft sum one. For example, place mass one at the root and divide each internal vertex's mass equally between its children; a leaf at depth $l$ receives $2^{-l}$, and the total mass on leaves remains one. Using part d gives the two equationsMultiplying the second equation by $2^s$ and subtracting the first gives the uniform-source Huffman length distributionIf $m=2^s$, the first number is zero and every codeword has length $s$. Otherwise both levels occur. The corresponding mean length is $L=s-(2^s-m)/m$.