# Huffman tree and maximum depth

Knowing the frequencies of each symbol, is it possible to determine the maximum height of the tree without applying the Huffman algorithm? Is there a formula that gives this tree height?

• Try playing around with a few examples, and see if you can find any useful criterion. That's what I would do if I were trying to answer your question, but it's probably better for you to do it yourself... Feb 6, 2014 at 19:14
• Yes, I've already tried with a lot of examples, but I'm looking for a litteral expression, for instance an asymptotic bound, function of the number of symbols... Feb 6, 2014 at 19:35
• In terms of the number of symbols, you can't do anything better than $n-1$ on the one hand, and $\lceil \log_2 n \rceil$ on the other. Feb 6, 2014 at 21:20
• Sorry. I was thinking about the number of symbols and their frequencies. For instance, maybe it is possible to give the maximal depth by looking simply the lowest frequency among all the symbols ? $n-1$ is a rought bound on the depth, I'm interested in a tight bound. Feb 6, 2014 at 21:24
• I would try to look at $\max -\log_2 p_i$ and see if it's related to the depth. You can also try to come up with the recursion corresponding to the actual algorithm, and see if it gives you anything. Feb 6, 2014 at 22:32