# Problem with determining the shape and direction of the Huffman Diagram

I have the phrase "abracadabra" and I want to encode it through the Huffman method. I first took the frequencies of each letters; $$a=5$$ $$b=3$$ $$c=1$$ $$d=2$$ $$r=2$$ But I'm not sure as to how the diagram should look like. I made a few and some of them are correct. Also what determines the direction the branches take? Is there any fixed criteria for it?

• Why is $v$ 100 in your second tree? Why do $c,d,r$ begin with 11 rather than 01 in your third tree? Commented Mar 30, 2018 at 17:58

## 1 Answer

Huffman's algorithm is non-deterministic — at several junctures you have more than one admissible choice. For example, at the first step, you can merge either $c$ and $d$ or $c$ and $r$. As another example, you can choose which child is left and which is right arbitrarily. Any particular implementation of Huffman's algorithm has some tie-breaking rule which makes it deterministic, but any choice would lead to a minimum redundancy code, and the generic Huffman algorithm doesn't specify any specific tie-breaking rule.

Huffman's algorithm is guaranteed to produce a minimum redundancy code, but not every minimum redundancy code can be produced by an admissible run of Huffman's algorithm. See Gallager's classic paper Variations on a theme by Huffman.