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
  • $\begingroup$ What do you mean by "one of the Huffman trees"? What is a Huffman tree of a series? The details matter here! $\endgroup$ Nov 20, 2017 at 12:32
  • $\begingroup$ @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. $\endgroup$
    – Yos
    Nov 20, 2017 at 12:35
  • $\begingroup$ 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. $\endgroup$ Nov 20, 2017 at 12:36
  • $\begingroup$ 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. $\endgroup$
    – Yos
    Nov 20, 2017 at 12:38
  • $\begingroup$ 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. $\endgroup$ Nov 20, 2017 at 12:40

1 Answer 1


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.

Note that Huffman's algorithm, as described in your textbook, is non-deterministic in the sense that at any step there could be many valid choices. Any actual implementation of the algorithm will use a tie-breaking rule to arbitrarily choose which two leaves of minimal probability to merge at any given step.

  • $\begingroup$ So essentially I can claim that Huffman algorithm "could have chosen" the two leaves because it's one of the possible options? Do we know how many options there are? $\endgroup$
    – Yos
    Nov 20, 2017 at 14:23
  • 1
    $\begingroup$ 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). $\endgroup$ Nov 20, 2017 at 14:24
  • $\begingroup$ if we're interested in order why is it not Perm(m,2)? $\endgroup$
    – Yos
    Nov 20, 2017 at 14:29
  • $\begingroup$ I have no idea what Perm(m,2) is. $\endgroup$ Nov 20, 2017 at 14:30
  • 1
    $\begingroup$ You can check that $P(m,2) = m(m-1)$. $\endgroup$ Nov 20, 2017 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.