# Prove the Prefix Code Tree in Huffman Coding is Optimal

Lemma: Let $$a$$ and $$b$$ be two characters that are sibling leaves of maximum depth $$T$$, and $$x$$ and $$y$$ are the two charachterts of the minimum frequency $$f(\cdot)$$. WLOG, assume that $$f[x] . Then we must have $$d_T(x) = d_T(y) =d_T(a) =d_T(b)$$.

Definitions: $$d_T(x)$$ is the depth of a character in the tree. We can define the cost as the number of bits needed to encode tree $$B(T)=\Sigma_{\forall c \in C}f(c)\times d_T(c)$$.

We can exchange characters of $$x$$ and $$a$$. This exchange yeilds another tree $$T'$$, so the difference of cost $$B(T) - B(T')$$ yeilds that $$(f[a] - f[x])(d_T(a)-d_T(x)) \ge 0$$. Then we can show that $$d_T(a)=d_T(x)\blacksquare$$.

Problem: Why we assume in the beginning that $$d_T(x) = d_T(y) =d_T(a) =d_T(b)$$ please given that $$x$$ has the least frequency and thus has the maximum depth $$d_T(x)$$, so I am not sure why it was assumed depths are equal and then we also indeed proved they are?

• That's not assumed, it's stated by the lemma. Oct 12 at 18:56