PadhaikoAll subjects

Past exam question: 2078 Chaitra (Regular), Q7

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Definition and tree terminologies · Binary trees · Binary search tree

Question

Construct a Huffman code for the given symbols.

SymbolABCDEF
Frequency (in thousands)3518102098

Solution

Arrange Symbols by Frequency (Min-Priority Queue): Initial sorted frequencies: F(8), E(9), C(10), B(18), D(20), A(35) (total frequency = ).

Greedy Tree Merging:

  1. Merge two smallest: F(8) and E(9) FE(17). Remaining: C(10), FE(17), B(18), D(20), A(35).
  2. Merge two smallest: C(10) and FE(17) CFE(27). Remaining: B(18), D(20), CFE(27), A(35).
  3. Merge two smallest: B(18) and D(20) BD(38). Remaining: CFE(27), A(35), BD(38).
  4. Merge two smallest: CFE(27) and A(35) CFEA(62). Remaining: BD(38), CFEA(62).
  5. Merge remaining two: BD(38) and CFEA(62) Root(100).

Huffman Tree and Code Assignment (0 = left, 1 = right):

               (100)
              /     \
           (38)     (62)
           /  \     /   \
         B(18) D(20) (27) A(35)
                    /    \
                  C(10)  (17)
                        /    \
                      F(8)   E(9)

Reading root-to-leaf paths:

SymbolFrequencyCodewordLengthWeighted Bits
A3511270
B1800236
D2001240
C10100330
F81010432
E91011436

Average code length = bits/symbol.

Answer:

Huffman codes (0 left, 1 right): A = 11, B = 00, D = 01, C = 100, F = 1010, E = 1011 (average code length = bits/symbol).

All past exam questions for Data Structure and Algorithms