Huffman Encoding in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Huffman Encoding Tree Construction

What is the output of the following code that builds a Huffman tree and prints the codes for each character?

DSA C

typedef struct Node {
    char ch;
    int freq;
    struct Node *left, *right;
} Node;

// Assume a min-heap and tree building functions are implemented correctly

// Characters and frequencies
char chars[] = {'a', 'b', 'c', 'd', 'e', 'f'};
int freq[] = {5, 9, 12, 13, 16, 45};

// After building Huffman tree, codes are printed
// Output format: character: code
// For example: a: 110

// The expected codes are:
// f: 0
// c: 100
// d: 101
// a: 1100
// b: 1101
// e: 111

// The printed output is:
// f: 0
// c: 100
// d: 101
// a: 1100
// b: 1101
// e: 111

A { "f": "111", "c": "110", "d": "101", "a": "100", "b": "0", "e": "10" }

B { "a": "0", "b": "10", "c": "110", "d": "1110", "e": "11110", "f": "11111" }

C { "a": "00", "b": "01", "c": "10", "d": "110", "e": "111", "f": "1" }

D { "f": "0", "c": "100", "d": "101", "a": "1100", "b": "1101", "e": "111" }

💡 Hint

Recall that characters with higher frequency get shorter codes in Huffman encoding.

The Huffman tree built from the given frequencies assigns the shortest code to 'f' (highest frequency) and longer codes to less frequent characters. Option D matches the correct Huffman codes.

🧠 Conceptual

intermediate

Minimum Number of Bits in Huffman Encoding

Given characters with frequencies: {'x': 10, 'y': 15, 'z': 30}, what is the minimum total number of bits needed to encode the string "xyzxyz" using Huffman encoding?

A 12 bits

B 16 bits

C 10 bits

D 14 bits

💡 Hint

Calculate the Huffman codes for each character and multiply by their occurrences in the string.

The Huffman codes assign shorter codes to higher frequency characters. For "xyzxyz", total bits = sum of (code length * frequency in string). Option C matches the correct calculation.

🔧 Debug

advanced

Identify the Error in Huffman Tree Node Comparison

What error does the following C code snippet cause when used in building a Huffman tree? typedef struct Node { char ch; int freq; struct Node *left, *right; } Node; int compare(const void *a, const void *b) { Node *nodeA = (Node *)a; Node *nodeB = (Node *)b; return nodeA->freq - nodeB->freq; } // Used in qsort to sort array of Node pointers

A Incorrect sorting because pointers are not dereferenced properly

B Segmentation fault due to incorrect pointer casting

C Compilation error due to incompatible pointer types

D No error; code works correctly

💡 Hint

Consider what qsort passes to the compare function when sorting pointers.

qsort passes pointers to elements, so when sorting an array of Node pointers, the compare function receives pointers to pointers. The code casts to Node* instead of Node** and dereferences incorrectly, causing wrong sorting.

🚀 Application

advanced

Huffman Encoding Compression Ratio Calculation

A file contains 1000 characters: 400 'A's, 300 'B's, 200 'C's, and 100 'D's. Using Huffman encoding, what is the approximate compression ratio compared to fixed-length 2-bit encoding per character?

A Compression ratio is approximately 1.25 (25% smaller)

B Compression ratio is approximately 0.6 (40% smaller)

C Compression ratio is approximately 0.8 (20% smaller)

D Compression ratio is approximately 0.5 (50% smaller)

💡 Hint

Calculate average bits per character using Huffman codes and compare with fixed 2 bits per character.

Fixed-length encoding uses 2 bits per character. Huffman encoding assigns shorter codes to frequent characters, reducing average bits per character. Calculating weighted average bits per character gives about 1.2 bits, so compression ratio = 1.2/2 = 0.6.

🧠 Conceptual

expert

Huffman Encoding Tree Uniqueness

Which statement about the uniqueness of Huffman encoding trees is correct when multiple characters have the same frequency?

A Multiple valid Huffman trees can exist if characters have equal frequencies

B Huffman encoding tree is always unique regardless of frequency ties

C Huffman tree uniqueness depends on the order characters appear in the input string

D Huffman tree is unique only if all frequencies are distinct prime numbers

💡 Hint

Consider how the algorithm chooses nodes when frequencies are equal.

When frequencies tie, the order of combining nodes can vary, leading to different valid Huffman trees with different codes but same total cost.