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?