Do the two huffman trees have the same corpus?

Question

Consider the following Huffman trees:

I was asked if those trees can have the same corpus. My answer was no, based on these calculations:

For the right tree:
$a_1 \le a_2$
$a_1 + a_2 \le a_5$
$a_3 \le a_4$
$a_1 + a_2 + a_5 \le a_3 + a_4$

For the left tree:
$a_1 \le a_2$
$a_3 \le a_4$
$a_1 + a_2 + a_3 + a_4 \le a_5$

Adding the last equations from each tree we have that:
$2a_1 + 2a_2 \le 0$ Which is a contradiction because frequency cannot be negative.

Nevertheless, I understood that there is a possibility that the two trees would have the same corpus. For instance, consider $1,1,1,2,3$.

So, where do my calculations go wrong?

Answer 1

Your inequalities are based on the assumption that the left child of an inner node is not bigger than the right child. However, this does not hold. (Note that the condition is violated for the root of the right tree.)

Instead we do know that whenever the algorith chose to unite two nodes, there were no nodes with smaller weight present. For the left tree we find:

• $a_1$ ad $a_2$ were joined before $a_5$ was joined to another node, so $$a_1 \leq a_5\text{ and }a_2\leq a_5.$$
• We do not know, if $a_1$ and $a_2$ were joined before or after $a_3$ and $a_4$, but in case the latter pair was joined first, we find $a_1 \leq a_3+a_4$ and $a_2\leq a_3+a_4$. If the former pair was joined first, we find $a_1\leq a_3$, $a_2\leq a_3$, $a_1\leq a_4$, and $a_2 \leq a_4$. These inequalities imply those of the first case, so we can conclude that $$a_1 \leq a_3+a_4 \text{ and } a_2\leq a_3+a_4.$$

Can you go on from here?