803 views

1 Answer

4 votes
4 votes

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/

Related questions

1 votes
1 votes
2 answers
1
Akash Kumar Roy asked Apr 26, 2018
3,932 views
what is Space complexity of Huffman coding?
1 votes
1 votes
3 answers
3
Parshu gate asked Nov 16, 2017
2,589 views
The following message is: GATE2018GAATTTEEEE22000011188What is the average length of bits required for encoding each letter using Huffman coding___?
2 votes
2 votes
1 answer
4
atul_21 asked Nov 13, 2017
682 views