Note that the property by which you are defining the Huffman encoding is not entirely obvious from the algorithm, and was not stated in your original node.

Certainly I had no idea what you meant. I had a distinct impression that we were to come up with another tree which could be produced by the same algorithm as the first. I think it would have really helped to have some complex inputs and complex outputs. Or to have a program which could be used to validate things.

Otherwise I guarantee that, for instance, someone will try to get the bonus and (for instance) use a naive recursive algorithm get the wrong result on the case where a-r are weighted 1 each, and S and T get 3. The ouput should be:

a 1 00000
b 1 00001
c 1 00010
d 1 00011
e 1 00100
f 1 00101
g 1 00110
h 1 00111
i 1 01000
j 1 01001
k 1 01010
l 1 01011
m 1 01100
n 1 01101
o 1 01110
p 1 01111
q 1 1000
r 1 1001
S 3 101
T 3 11
[download]

However a recursive approach will have a hard time figuring out where is globally best to take the penalties of incorrect weights.