Huffman Encoding in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Huffman Tree Construction

What is the output of the following code that builds a Huffman tree and prints the root frequency?

DSA Python

import heapq

class Node:
    def __init__(self, freq, char=None, left=None, right=None):
        self.freq = freq
        self.char = char
        self.left = left
        self.right = right
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(freq_map):
    heap = [Node(freq, char) for char, freq in freq_map.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = Node(left.freq + right.freq, None, left, right)
        heapq.heappush(heap, merged)
    return heap[0]

freq_map = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
root = build_huffman_tree(freq_map)
print(root.freq)

A 100

B 45

C 50

D 60

💡 Hint

Sum all frequencies to find the root frequency.

The root frequency is the sum of all character frequencies: 5+9+12+13+16+45 = 100.

🧠 Conceptual

intermediate

Huffman Encoding Bit Length Calculation

Given the frequencies {'x': 3, 'y': 3, 'z': 4}, what is the total number of bits required to encode the string "xyzxyz" using Huffman encoding?

A 12

B 9

C 8

D 10

💡 Hint

Calculate the Huffman codes and multiply by character counts.

The Huffman codes assign 2 bits for 'x' and 'y', and 1 bit for 'z'. Encoding "xyzxyz" requires 2*2 + 2*2 + 2*1 = 10 bits.

🔧 Debug

advanced

Identify the Error in Huffman Encoding Function

What error does the following code raise when trying to encode a string using Huffman codes?

DSA Python

def encode_string(s, codes):
    result = ''
    for ch in s:
        result += codes[ch]
    return result

codes = {'a': '0', 'b': '10', 'c': '11'}
print(encode_string('abcx', codes))

A No error, outputs '01011x'

B KeyError

C IndexError

D TypeError

💡 Hint

Check if all characters in the string have codes.

The character 'x' is not in the codes dictionary, so accessing codes['x'] raises a KeyError.

🚀 Application

advanced

Huffman Decoding Result

Given the Huffman codes {'a': '0', 'b': '10', 'c': '11'}, what is the decoded string of the bit sequence '0110'?

A "abb"

B "baa"

C "abc"

D "aab"

💡 Hint

Decode bits step by step using the codes.

The bit sequence '0110' can be split as '0' (a), '10' (b), '10' (b) to get 'abb'.

🧠 Conceptual

expert

Minimum Weighted Path Length in Huffman Tree

For a set of characters with frequencies {A: 1, B: 1, C: 2, D: 3, E: 5}, what is the minimum weighted path length (sum of frequency * code length) of the Huffman encoding?

A 14

B 15

C 13

D 17

💡 Hint

Build the Huffman tree and calculate sum(freq * depth).

The optimal Huffman tree assigns code lengths so that the sum of frequency times code length is 13.

Practice

1. What is the main purpose of Huffman Encoding in data compression?

easy

A. To encrypt data for security

B. To assign equal length codes to all characters

C. To assign shorter codes to more frequent characters

D. To sort characters alphabetically

Solution

1. Step 1: Understand Huffman Encoding goal

   Huffman Encoding aims to reduce the total bits used by assigning shorter codes to characters that appear more often.

2. Step 2: Compare options with this goal

   Only To assign shorter codes to more frequent characters matches this goal. Options B, C, and D do not describe Huffman Encoding's purpose.

3. Final Answer:

   To assign shorter codes to more frequent characters -> Option C

4. Quick Check:

   Huffman Encoding = shorter codes for frequent chars [OK]

Hint: Remember: frequent chars get shorter codes in Huffman [OK]

Common Mistakes:

• Thinking Huffman assigns equal length codes
• Confusing Huffman with encryption
• Assuming it sorts characters alphabetically

2. Which Python data structure is commonly used to build the Huffman tree efficiently?

easy

A. List

B. Heap (priority queue)

C. Dictionary

D. Queue

Solution

1. Step 1: Identify data structure for minimum frequency extraction

   Huffman tree construction repeatedly extracts two nodes with the smallest frequencies.

2. Step 2: Choose data structure supporting efficient min extraction

   A heap (priority queue) allows quick access to the smallest element, making it ideal.

3. Final Answer:

   Heap (priority queue) -> Option B

4. Quick Check:

   Min extraction = heap (priority queue) [OK]

Hint: Use a heap for fast smallest frequency access [OK]

Common Mistakes:

• Using a list without sorting repeatedly
• Choosing a queue which is FIFO, not min-based
• Assuming dictionary stores order

3. What is the output of the following Python code snippet that builds a Huffman tree for characters with frequencies {'a': 5, 'b': 9, 'c': 12}?

import heapq
freq = [('a', 5), ('b', 9), ('c', 12)]
heap = [(f, ch) for ch, f in freq]
heapq.heapify(heap)
while len(heap) > 1:
    f1, ch1 = heapq.heappop(heap)
    f2, ch2 = heapq.heappop(heap)
    heapq.heappush(heap, (f1 + f2, ch1 + ch2))
print(heap[0])

medium

A. (26, 'cab')

B. (26, 'abc')

C. (26, 'cba')

D. (26, 'bac')

Solution

1. Step 1: Initialize heap with frequencies

   Heap contains (5,'a'), (9,'b'), (12,'c'). After heapify, smallest frequency is (5,'a').

2. Step 2: Combine two smallest nodes repeatedly

   Pop (5,'a') and (9,'b'), combine to (14,'ab'), push back. Heap now has (12,'c') and (14,'ab'). Pop (12,'c') and (14,'ab') and combine to (26,'cab').

3. Final Answer:

   (26, 'cab') -> Option A

4. Quick Check:

   Sum freq = 5+9+12 = 26, combined chars 'cab' [OK]

Hint: Sum frequencies and combine chars in order popped [OK]

Common Mistakes:

• Mixing character order in combined string
• Adding frequencies incorrectly
• Not heapifying before popping

4. Identify the error in this Huffman tree building code snippet:

import heapq
freq = {'a': 3, 'b': 2, 'c': 6}
heap = []
for ch, f in freq.items():
    heapq.heappush(heap, (ch, f))
while len(heap) > 1:
    f1, ch1 = heapq.heappop(heap)
    f2, ch2 = heapq.heappop(heap)
    heapq.heappush(heap, (f1 + f2, ch1 + ch2))
print(heap[0])

medium

A. Incorrect loop condition in while

B. Heap elements pushed with frequency first, character second

C. Using heappush instead of heapify

D. Heap elements pushed with character first, frequency second

Solution

1. Step 1: Check heap element structure

   Heap elements must be tuples with frequency first for correct min-heap behavior.

2. Step 2: Identify error in heappush order

   Code pushes (ch, f) instead of (f, ch), so heap compares characters, not frequencies.

3. Final Answer:

   Heap elements pushed with character first, frequency second -> Option D

4. Quick Check:

   Frequency must be first in heap tuple [OK]

Hint: Push (frequency, character) tuples to heap [OK]

Common Mistakes:

• Swapping frequency and character order
• Not using heapify for initial heap
• Wrong while loop condition

5. Given the frequencies {'x': 4, 'y': 7, 'z': 8, 'w': 15}, what is the Huffman code for character 'w' after building the tree? Assume left edge is '0' and right edge is '1'.

hard

A. '0'

B. '11'

C. '1'

D. '10'

Solution

1. Step 1: Build Huffman tree with given frequencies

   Initial heap: (4,'x'), (7,'y'), (8,'z'), (15,'w'). Combine smallest: (4,'x') + (7,'y') = (11,'xy'). Heap now (8,'z'), (11,'xy'), (15,'w'). Combine (8,'z') + (11,'xy') = (19,'zxy'). Heap now (15,'w'), (19,'zxy'). Combine (15,'w') + (19,'zxy') = (34,'wzxy').

2. Step 2: Assign codes from root to leaves

   Root splits into left child (15,'w') and right child (19,'zxy'). 'w' is left child, so code is '0'.

3. Final Answer:

   '0' -> Option A

4. Quick Check:

   'w' is left child of root = '0' [OK]

Hint: Largest freq often gets shortest code at root edge [OK]

Common Mistakes:

• Assigning 'w' code as '1' instead of '0'
• Confusing left/right edges
• Not building tree stepwise