Average codeword length is the same in any Huffman encoding schemes

Question

I have to prove that the average codeword length is the same in any Huffman encoding schemes for a source S.

The average codeword length is equal to the sum of the codeword lengths times the probability of their source symbols.

If while constructing a Huffman tree for a source S and no two nodes in the top row ever have the same probability, then there would only be one Huffman tree and thus one encoding scheme and average codeword length.

However, if two or more nodes in the top row have the same probability, then it would be possible to switch the nodes of the same probability while constructing the Huffman tree, such that the encoding scheme would have the same codewords (and thus the same average codeword length) but corresponding to different source symbols.

But this only works if the different Huffman trees are essentially the same. How can I expand this to encoding schemes with different codeword lengths (but with the same average codeword length)?

Edit: I know that if the probability of j is larger than that of k, then the length of j will be less than the length of k.

Answer 1

Let me suggest a sledgehammer:

1. Prove that the greedy algorithm is optimal, that is, the average codeword length is minimum. (e.g. http://www.ida.liu.se/opendsa/OpenDSA/Books/OpenDSA/html/HuffProof.html)
2. By the definition of Huffman coding schemes, all schemes (isomorphic or not) have minimum average codeword length.