Search code examples
algorithmhuffman-code

Huffman Code Tree with Depth 1 less than number of letters

I need to create a Huffman Code tree using n letters and make the tree of depth n-1.

I tried making all the frequencies equal but it did not work for some values of n.

Is there any specific way to solve this

Solution

  • The set of frequencies to do this with the minimum sum is a modification of the Lucas numbers.

    The Lucas number sequence starts with 2, 1, and continues with each number being the sum of the previous two numbers (just like the Fibonacci sequence, which instead starts with 1, 1).

    2 1 3 4 7 11 18 29 47 ...

    To get the longest Huffman code, replace that initial 2 with 1, 1:

    1 1 1 3 4 7 11 18 29 47 ...

    That sequence of n frequencies will result in the maximal-length Huffman code of n-1 bits.

    The depth-nine tree is:

    deep tree