What is the Huffman Tree?

Relevant wiki: Huffman Code

The elements with the smallest probabilities are B, C, D, and E. We will arbitrarily choose D and E to be the first subtree. We update our list to remove D and E, and add subtree DE with probability $.1 + .1 = .2$ .

The next two elements with the smallest probability are B and C. We update our list to remove B and C, and add subtree BC with probability $.1 + .1 = .2$ .

The next two elements with the smallest probability are BC and DE. We update our list to remove BC and DE, and add subtree BCDE with probability $.2 + .2 = .4$ .

Finally, we combine the last two elements to get ABCDE with a probability of 1.

This Huffman tree resembles tree #3.

B, C, D and E have the same probability, so they must need the same number of steps to get to them. The only tree which follows this is the third one.