# Proof of codeword length (Huffman)

Question. There's guarantee to be codeword of length 1 if some characters occur frequency > 2/5.

hypothetical tree with no codewords of length 1

Proof: Assume for the purpose of obtaining a contradiction that there is no codeword of length $1$. Then both children of the root can not be leaves. Let the left child of the root be $L$, right child $R$, and the two children of each subtree $a, b$, and $c, d$ respectively.

Without loss of generality assume that the character with frequency greater than $2/5$ appears in the subtree $a$ of the left child of the root. The right subtree $R$ will have to have combined weight more than $2/5$, since otherwise $R$ being smaller than $a$ would be joined first with $b$. The combined weight on $b$ will be less than $1/5$ since the total sum of frequencies has to add up to $1$.

I understand the first paragraph of the proof. But I'm having trouble understanding the second paragraph. Why frequency of $R$ has to be $< 3/5$ just because frequency of $a$ $> 2/5$? My understanding is $R$ can be greater than $a$ but less than $L$.

At the same time, the right subtree has to have cumulative weight less than $3/5$, since one of the elements in $L$ has frequency in excess of $2/5$. One of the two subtrees of $R$ has to have weight less then $3/10$, but then it would be combined with subtree $b$, since the total weight of $R$ is greater than $2/5$ and so the other subtree of $R$ would have weight greater than that of $b$.

This is a contradiction, since $b$ was joined with $a$, so there is guaranteed to be a codeword of length $1$.

The total weight of all the elements is $1$. The total weight of $R$ is the sum of the weights of its elements, and the total weight of $L$ is the sum of the weights of its elements, and every element is in exactly one of these subtrees, so the weight of $R$ plus the weight of $L$ must be $1$. Let $r$ be the weight of $R$ and $\ell$ the weight of $L$. $L$ has an element whose weight is more than $\frac25$, so $\ell>\frac25$, and therefore

$$r=1-\ell<1-\frac25=\frac35\;.$$

• That clears up. Thanks!! – user3273345 Oct 22 '15 at 20:02
• @user3273345: You’re welcome! – Brian M. Scott Oct 22 '15 at 20:02