# 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... – Yuval Filmus Feb 6 '14 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... – user7060 Feb 6 '14 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. – Yuval Filmus Feb 6 '14 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. – user7060 Feb 6 '14 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. – Yuval Filmus Feb 6 '14 at 22:32