Search code examples
calgorithmdata-structureshuffman-code

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

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.

Solution

  • 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.