Huffman Encoding in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Huffman Tree Construction

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

DSA C++

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

struct Node {
    char ch;
    int freq;
    Node *left, *right;
    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(Node* l, Node* r) {
        return l->freq > r->freq;
    }
};

void printCodes(Node* root, string str) {
    if (!root) return;
    if (!root->left && !root->right) {
        cout << root->ch << ":" << str << " ";
    }
    printCodes(root->left, str + "0");
    printCodes(root->right, str + "1");
}

int main() {
    unordered_map<char, int> freq = {{'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}};
    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (auto pair : freq) {
        pq.push(new Node(pair.first, pair.second));
    }
    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        Node* merged = new Node('$', left->freq + right->freq);
        merged->left = left;
        merged->right = right;
        pq.push(merged);
    }
    Node* root = pq.top();
    printCodes(root, "");
    return 0;
}

A f:0 a:1100 b:1101 c:100 d:101 e:111

B f:1 a:000 b:001 c:010 d:011 e:100

C f:0 a:100 b:101 c:110 d:111 e:11

D f:0 a:111 b:110 c:101 d:100 e:11

💡 Hint

Focus on how the priority queue merges nodes with lowest frequencies first.

The Huffman tree merges nodes with the smallest frequencies first, assigning shorter codes to more frequent characters. 'f' has the highest frequency and gets the shortest code '0'. The codes for other characters follow from the tree structure.

🧠 Conceptual

intermediate

Huffman Encoding Tree Property

Which property is always true for a Huffman encoding tree built from a set of character frequencies?

A The tree is a full binary tree where every internal node has exactly two children.

B The tree is always a complete binary tree with all levels fully filled except possibly the last.

C The tree is a balanced binary tree with equal height on left and right subtrees.

D The tree is a binary search tree sorted by character ASCII values.

💡 Hint

Think about how nodes are merged in pairs during construction.

Huffman trees are full binary trees because each internal node is created by merging exactly two nodes, so every internal node has two children.

🔧 Debug

advanced

Identify the Error in Huffman Encoding Code

What error will the following C++ code produce when run?

DSA C++

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

struct Node {
    char ch;
    int freq;
    Node *left, *right;
    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(Node* l, Node* r) {
        return l->freq < r->freq; // Note the comparison direction
    }
};

int main() {
    unordered_map<char, int> freq = {{'a', 5}, {'b', 9}};
    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (auto pair : freq) {
        pq.push(new Node(pair.first, pair.second));
    }
    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        Node* merged = new Node('$', left->freq + right->freq);
        merged->left = left;
        merged->right = right;
        pq.push(merged);
    }
    cout << pq.top()->freq << endl;
    return 0;
}

A The code runs but causes an infinite loop

B The code runs and prints 9

C The code runs and prints 5

D The code runs and prints 14

💡 Hint

Check the priority queue comparison operator and how it affects the order.

The comparison operator uses '<', making the priority_queue a max-heap (pops largest frequencies first). With only two nodes, it still correctly merges them and prints the total frequency 14.

🚀 Application

advanced

Calculate Total Bits for Huffman Encoding

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

A 150 bits

B 180 bits

C 160 bits

D 155 bits

💡 Hint

Build the Huffman tree, assign codes, then multiply code length by frequency and sum.

The Huffman codes are: w=0 (1 bit), z=11 (2 bits), y=101 (3 bits), x=100 (3 bits). Total bits = 45*1 + 30*2 + 15*3 + 10*3 = 45 + 60 + 45 + 30 = 180 bits.

❓ Predict Output

expert

Output of Huffman Decoding Function

What is the output of the following C++ code that decodes a Huffman encoded string?

DSA C++

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

string decodeHuffman(string encoded, unordered_map<string, char> codeMap) {
    string result = "";
    string temp = "";
    for (char bit : encoded) {
        temp += bit;
        if (codeMap.find(temp) != codeMap.end()) {
            result += codeMap[temp];
            temp = "";
        }
    }
    return result;
}

int main() {
    unordered_map<string, char> codeMap = {{"0", 'a'}, {"10", 'b'}, {"110", 'c'}, {"111", 'd'}};
    string encoded = "010110111010";
    cout << decodeHuffman(encoded, codeMap) << endl;
    return 0;
}

A acbdab

B acdbab

C abcdab

D abdcab

💡 Hint

Match bits from left to right using the code map to decode characters.

Decoding steps: '0' -> 'a' '10' -> 'b' '110' -> 'c' '111' -> 'd' '0' -> 'a' '10' -> 'b' Decoded string: abcdab. Matches option C.

Practice

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

easy

A. To sort characters alphabetically

B. To assign equal length codes to all characters

C. To encrypt data for security

D. To assign shorter codes to more frequent characters

Solution

1. Step 1: Understand Huffman Encoding goal

   Huffman Encoding aims to reduce the total number of bits by giving 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 A, B, and C do not describe Huffman Encoding correctly.

3. Final Answer:

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

4. Quick Check:

   Huffman Encoding = shorter codes for frequent chars [OK]

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

Common Mistakes:

• Thinking Huffman assigns equal length codes
• Confusing encoding with encryption
• Assuming sorting is the main goal

2. Which of the following C++ code snippets correctly declares a priority queue to build a Huffman tree based on character frequencies?

easy

A. std::priority_queue, std::vector>, std::greater<>> pq;

B. std::priority_queue> pq;

C. std::priority_queue> pq;

D. std::priority_queue, std::vector>, std::less<>> pq;

Solution

1. Step 1: Identify priority queue type for Huffman

   Huffman requires a min-heap priority queue to get the smallest frequency first. std::greater<> creates a min-heap.

2. Step 2: Check each option

   std::priority_queue, std::vector>, std::greater<>> pq; uses std::greater<> with pair, which is correct. Options B and C default to max-heap. std::priority_queue, std::vector>, std::less<>> pq; uses std::less<> which is max-heap.

3. Final Answer:

   std::priority_queue, std::vector>, std::greater<>> pq; -> Option A

4. Quick Check:

   Min-heap priority queue = std::priority_queue, std::vector>, std::greater<>> pq; [OK]

Hint: Use std::greater<> for min-heap in priority_queue [OK]

Common Mistakes:

• Using default max-heap instead of min-heap
• Swapping pair elements order incorrectly
• Forgetting to specify comparator

3. Given the frequencies: {'a': 5, 'b': 9, 'c': 12, 'd': 13}, what is the Huffman code for character 'a' after building the Huffman tree?

medium

A. 111

B. 00

C. 110

D. 10

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies: 5('a') + 9('b') = 14, then combine 12('c') + 13('d') = 25, then combine 14 + 25 = 39.

2. Step 2: Assign codes from tree

   'a' is in the left subtree of the first combined node, so it gets code '110' (left-right-left). Other codes differ.

3. Final Answer:

   110 -> Option C

4. Quick Check:

   'a' gets code = 110 [OK]

Hint: Lowest freq chars get codes with more leading zeros [OK]

Common Mistakes:

• Assigning wrong code by mixing tree branches
• Confusing 'a' code with 'b' or 'c'
• Not building tree stepwise

4. Identify the error in this C++ snippet for building a Huffman tree:

std::priority_queue, Compare> pq;
while(pq.size() > 1) {
  Node* left = pq.top(); pq.pop();
  Node* right = pq.top(); pq.pop();
  Node* parent = new Node(left->freq + right->freq, left, right);
  pq.push(parent);
}

medium

A. The loop condition should be pq.size() >= 1

B. The priority queue comparator Compare is missing or incorrect

C. Nodes should be popped after pushing the parent

D. The parent node frequency calculation is wrong

Solution

1. Step 1: Check priority queue usage

   Priority queue needs a comparator to order nodes by frequency ascending for Huffman. If Compare is missing or incorrect, ordering fails.

2. Step 2: Validate other parts

   Loop condition pq.size() > 1 is correct. Popping nodes before pushing parent is correct. Frequency sum is correct.

3. Final Answer:

   The priority queue comparator Compare is missing or incorrect -> Option B

4. Quick Check:

   Missing comparator breaks min-heap order [OK]

Hint: Always define comparator for priority_queue of pointers [OK]

Common Mistakes:

• Using wrong loop condition
• Popping nodes in wrong order
• Incorrect frequency sum

5. You have the string "abbcccdddd". Using Huffman Encoding, what is the total number of bits required to encode this string if the codes are assigned optimally?

hard

A. 19 bits

B. 22 bits

C. 24 bits

D. 20 bits

Solution

1. Step 1: Calculate character frequencies

   'a':1, 'b':2, 'c':3, 'd':4.

2. Step 2: Build Huffman tree and assign codes

   Combine lowest frequencies: 1+2=3, then 3+3=6, then 4+6=10. Codes assigned roughly: 'd' = 1 bit, 'c' = 2 bits, 'b' = 3 bits, 'a' = 3 bits.

3. Step 3: Calculate total bits

   Total bits = (1*3) + (2*3) + (3*2) + (4*1) = 3 + 6 + 6 + 4 = 19 bits.

4. Final Answer:

   19 bits -> Option A

5. Quick Check:

   Total bits = sum(freq * code length) = 19 [OK]

Hint: Multiply frequency by code length, then sum all [OK]

Common Mistakes:

• Mixing frequencies and code lengths
• Assigning wrong code lengths
• Adding frequencies instead of bits