 Solution

Make a rooted binary tree with an edge labelled zero for the first branch and one for the second branch at each interior node. Put each source symbol at the leaf reached by following the successive digits of its codeword. The prefix property ensures no assigned word ends at an ancestor of another assigned word.

The route of a codeword is its root-to-leaf path; its length is the number of edges on that path, equal to the number of binary digits in the word. For an optimal tree with positive leaf probabilities, every interior node has two children: a node with just one child could be contracted, shortening all words below it and strictly reducing the expected length. The diagram in the earlier Huffman calculation is one such full binary tree.