Greedy algo quiz - Huffman 2

#1

Q1. Huffman 2
Consider the following message: aabbbbabccdddccccbbdd
If Huffman tree is coded as left child with ‘0’ and right child with ‘1’ from every node then what is the decoded message for 110100?

abc

bcd

acb

bda

freq of a-3 b-7 c-6 d-5, so we should code
b - 0
c - 10
d - 110
a -1110
therefore 110100 should be decoded as “dcb”. but given answer is “bda” how??

#2

@snehacpcb_6a154f5c45187387,

  • For answer B , if we go left for 0 and right for 1 then
    11     -   right  –  right  = b

    01     - left  –   right     =  d

    00     - left   –  left       = a              Ans :-  **bda.**

image

#3

i see u have kindof maintained balanced tree… but that was not how it was shown on tutorial. He showed largest freq char as the left child of root and rest characters right child as a string, then we break the right child to futher left and right with second largest freq char as the left child and so on …

#4

can u clarify on this? if i go by ur method i definitely get right answers for all huffman questions just if u could check the huffman encoding video and clarify, it would be great.

#5

hi @snehacpcb_6a154f5c45187387 please ask the doubt on the huffman video ask doubt button so that i can have the video