# How to prove that for a full binary tree $T$ there's a series of frequencies such that Huffman alg. will produce $T$?

How to prove that for a full (each node that's not a leaf has 2 nodes) binary tree $T$ of $n$ leaves there's a series of frequencies $f_1,f_2,...,f_n$ such that if we use Huffman algorithm on the series we'll get $T$?

First in order to get frequencies from $T$ we can assign the probability of $\frac{1}{2^d}$ to each node where $d$ is the depth of a given node. The root node will have the probability of $1$ which means $100$%. After one traversal of $T$ we could fill the array with the frequencies of the leaves of $T$ (only leaves correspond to the the actual values to be encoded).

I'm not sure how to prove that if we apply Huffman algorithm to the frequencies one of the trees will happen to be $T$. It seems like if we build a tree from the frequencies each time such that the new tree is different (if possible) from the previous tree we'll eventually build $T$. Also we know that Huffman tree is always a full tree.

The Huffman algorithm is as follows (as described in Algorithm Design by Jon Kleinberg, Eva Tardos):

Huffman(S) {
if |S|=2 {
return tree with root and 2 leaves
} else {
let y and z be lowest-frequency letters in S
S’ = S
remove y and z from S’
insert new letter ω in S’ with f_ω=f_y+f_z
T’ = Huffman(S’)
T=add two children y and z to leaf ω from T’
return T
}
}

• What do you mean by "one of the Huffman trees"? What is a Huffman tree of a series? The details matter here! – Yuval Filmus Nov 20 '17 at 12:32
• @YuvalFilmus What I meant is that for any full binary tree there's a series of frequencies such that using Huffman algorithm on the frequencies will produce the original tree. Let me know if this makes sense. – Yos Nov 20 '17 at 12:35
• There are many possible variants of Huffman's algorithm, so we need to know which variant you are using. Also, the formulation of the question suggests that you're using a nondeterministic variant of Huffman's algorithm which could produce many different trees for the same distribution. – Yuval Filmus Nov 20 '17 at 12:36
• The Huffman algorithm I was referring to is the one described on page 172 (chpater 4) of the book Algorithm Design by Jon Kleinberg, Eva Tardos. – Yos Nov 20 '17 at 12:38
• Some of us don't have Kleinberg and Tardos's book. If you want those of us to help you with this exercise, you will have to describe this variant of the algorithm in your post. – Yuval Filmus Nov 20 '17 at 12:40

The proof is by induction. The case $n = 1$ is clear. For $n > 1$, choose two leaves at maximal depths, and merge them. Huffman's algorithm could have chosen these two leaves at the first step and merged them. Now apply the inductive hypothesis to complete the proof.
• If there are $m>1$ elements of minimum probability, then there are $m(m-1)$ options (or $\binom{m}{2}$ if you don't care about the order). If there is one element of minimum and $m$ of second minimum probability, then there are $2m$ options (or $m$ if you don't care about the order). – Yuval Filmus Nov 20 '17 at 14:24
• You can check that $P(m,2) = m(m-1)$. – Yuval Filmus Nov 20 '17 at 14:35