In the huffman coding algorithm, there's a lemma that says:
The binary tree corresponding to an optimal binary prefix code is full
But I can't figure out why. How can you prove this lemma?
From wikipedia,
A full binary tree (sometimes 2-tree or strictly binary tree) is a tree in which every node other than the leaves has two children.
The way in which the tree for huffman code is produced will definitely produce a full binary tree. Because at each step of the algorithm, we remove the two nodes of highest priority (lowest probability) from the queue and create a new internal node with these two nodes as children.