Prove: Every absolute binary tree can represent a Huffman series

Question

How can one prove that for every absolute binary tree (every node has either 0 or 2 children) there exists a Huffman series which can be represented by said tree.

Any hints will be much appreciated!

Answer 1

Constructive proof: if a_1, ..., a_k are the leaves' depths, then the series may be b_1 = 2^(-a_1), ..., b_k = 2^(-a_k).

1. Sum of all b_i = 1. Proof by induction: for one node this is true; two sibling leaves of depth A may be reduced to their parent and will give one node of depth A-1, while the sum of b_i will not change.
2. It can be proved almost the same way that b_i sequence may produce exactly the given tree if you use a Huffman algorithm.