# 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. Aug 15, 2016 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? Aug 15, 2016 at 13:52
• What research have you done? We expect you to search standard resources (e.g., Wikipedia, a standard textbook) for an answer before asking here. In this case, your question is already answered in the Wikipedia page on Huffman codes: "In general, a Huffman code need not be unique." There's little point in us repeating material that's already available in standard places. If your question is answered in the obvious place on Wikipedia, you probably ought to do more research before asking.
– D.W.
Aug 15, 2016 at 22:48

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.