# Huffman Tree Depth, Is there any theory?

I'd like to as a variation on this question regarding Huffman tree building. Is there any theory or rule of thumb to calculate the depth of a Huffman tree from the input (or frequency), without drawing tree.

Specific Example is : 10-Input Symbol with Frequency 1 to 10 is 5. the above question mentioned depth is 5.

Length-limited Huffman coding is a variant of Huffman coding where you are not allowed to use codewords longer than a given threshold. One can construct an optimal length-limited code in time $O(nL)$ where $n$ is the number of items and $L$ is the length bound; it is unknown whether this can be improved to match the time of unrestricted Huffman coding. See Larmore and Hirschberg, "A fast algorithm for optimal length-limited Huffman codes", JACM 1990, and Turpin and Moffat, "Practical length-limited coding for large alphabets", Computer J. 1995.
• It easy to show (I think) that if a symbol has probability $p$, then the length of its code word is at most $1+\log_2 (1/p)$ (or maybe 1+the ceiling of the log). That should be a good enough estimate for back of the envelope calculation, no? – Sariel Har-Peled Feb 17 '16 at 5:46
• True, but that estimate could be far from the actual code length. E.g. consider a Huffman code for two elements with probabilities $\epsilon$ (close to zero) and $1-\epsilon$; the length is 1, independent of $\epsilon$. – David Eppstein Feb 17 '16 at 7:55