Which node go in left or right on addition of weight while huffman tree creation

Question

I am trying to create a Huffman tree and i am bit confused by reading several links on internet. Some add the greater(in terms of weight) child nodes in left or some on right.

So my question:

(1)Is it really a matter that where to add the nodes(in left or right) ?

(2) May i add node with greater weight in right or lower weight in Left ?

Thanks for the help.

Answer 1

As long as you're consistent, it makes no difference.

Either you put all the lower weights on left children and all the higher weights on right children, or vice-versa.

At the bottom line, left and right will only be variable names in your code, with no physical meaning whatsoever.

UPDATE:

If you are not consistent, then the resulting Huffman tree will not necessarily yield the best possible compression that can be achieved for the given input using the Huffman compression algorithm.

Answer 2

It makes no difference, and it doesn't have to be consistent either. The currently accepted answer is wrong.

The reason is that:

• The depth of each encoded character in the tree is not affected by this decision;
• The Huffman decoding algorithm, gets the tree, so there is no meaning to "left" or "right"... at that moment it is only about distinctive symbol strings, consisting of symbols 0 or 1, which are implemented as bits, which uniquely define a character. There is no special meaning to the zero or to the one: the only importance is that they are distinct, and there is no ambiguity to which character a series defines.