Question

Prove that a binary tree that is not full cannot correspond to an optimal prefix code. The proof should first consider a prefix-free code C, whose corresponding binary tree T has some node with only one child; show that one can transform T into another binary tree T', whose corresponding code C' has smaller average length and so is better than C. In your proof you need to indicate the transformation from T into T' and explain why the code C' is better than C.

Answer 1

Here goes the proof:

Otherwise, let M be the parent of N, let T1 be the (possibly non-existent) sibling of N, and let T2​ be the subtree rooted at the child of N. Replace M by N, making the children of N the roots of subtrees T1​ and T2​. If T1​ is empty, repeat the process. We have a new prefix code (C') of lower cost, so the original was not optimal.