# Is huffman-encoding with distinct frequencies of symbols unique?

Say I have following text: "abbcccddddeeeee". As you can see, each letter has a different frequency of occurence. When making a Huffman-Trie to encode this String, will this trie be unique?

I thought a bit on the problem and I can't come to a definite conclusion, but I think the trie will NOT be unique. Say the begin-situation:

a(1) b(2) c(3) d(4) e(5)


To make a trie, we take the lowest frequencies together and make a node above it with the sum of those frequencies. Because the frequencies are all ascending, there is only 1 way to take the lowest nodes. In this case, a and b. If we keep going on further, it wel never occur that we need to choose 2 subtries out of a larger collection, there will always be just 2. When seeing this, you could conclude the trie will be unique BUT. I see never stated in which order the two subtries need to be added. For example, to make the first new subtrie, we can put node a left OR right of node B. We can do this at each level and eventually, this will flip some bits in the end-result.

Am I correct?

• No, Huffman trees are not unique, and moreover, there are minimum redundancy codes which are not Huffman codes. – Yuval Filmus Aug 15 '16 at 13:51
• I'm talking about total prefix-free codes. I think every Huffman trie results in prefix-free codes or isn't it? – CedricCornelis Aug 15 '16 at 13:52
2 3 4 5 is a counterexample:
4 5 5 (combine 2 and 3 to make 5, and reorder)
Now there are 2 choices for 4 to partner with: either the original 5, or the one formed by 2+3.