Question

What would be huffman coding for following : 

Character	Frequency
a	10
l	15
i	12
o	3
u	4
s	13
t	1

Explain this with suitable diagram..

Answer 1

Well, it seems like an easy one, but then the problem that arises here is that while solving the question, two nodes (subsequently) have same value ( 4 and 1 + 3 = 4). The challenge comes here.

So, after referring to the algorithms and the link (below, at the end), I got to the conclusion that when two nodes have same value, then choose the one you placed later in the queue (priority queue i.e min heap) as the node to be kept on left side.

For example, in the question, we add two nodes t + o = 1 + 3 = $4$ and place this result back into the queue (auto reordered as min heap rebuilt). Now, in queue, we have $u$ with $4$ and the sum of two nodes (t + o) also with value $4$. We had added t + o = $4$ later in the queue. So, we would place this on the left side in the tree. 

Rest of the problem is same as any other Huffman coding problem

Here is the tree for the answer

And here is the table

Symbol    Encoding
l          01
s          10
i          11
a          000
u          0010
o          00110
t          00111

References

For algorithm: http://www.geeksforgeeks.org/greedy-algorithms-set-3-huffman-coding/

For result verification: https://planetcalc.com/2481/