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 root node frequency?

DSA C#

using System;
using System.Collections.Generic;

class Node {
    public char? Symbol;
    public int Frequency;
    public Node Left, Right;
    public Node(char? symbol, int freq) {
        Symbol = symbol;
        Frequency = freq;
        Left = Right = null;
    }
}

class Program {
    static void Main() {
        var frequencies = new Dictionary<char, int> {{'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}};
        var pq = new SortedSet<(int freq, int id, Node node)>(Comparer<(int, int, Node)>.Create((x, y) => {
            int cmp = x.freq.CompareTo(y.freq);
            if (cmp == 0) return x.id.CompareTo(y.id);
            return cmp;
        }));
        int id = 0;
        foreach (var kvp in frequencies) {
            pq.Add((kvp.Value, id++, new Node(kvp.Key, kvp.Value)));
        }
        while (pq.Count > 1) {
            var first = pq.Min; pq.Remove(first);
            var second = pq.Min; pq.Remove(second);
            var merged = new Node(null, first.freq + second.freq);
            merged.Left = first.node;
            merged.Right = second.node;
            pq.Add((merged.Frequency, id++, merged));
        }
        var root = pq.Min.node;
        Console.WriteLine(root.Frequency);
    }
}

A 130

B 100

C 120

D 110

💡 Hint

Sum all frequencies to find the root frequency.

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

🧠 Conceptual

intermediate

Huffman Encoding Code Length Calculation

Given a Huffman tree built from characters with frequencies {'a': 3, 'b': 2, 'c': 6, 'd': 8}, what is the total number of bits needed to encode the string "abcd" using the Huffman codes?

A 7 bits

B 11 bits

C 10 bits

D 9 bits

💡 Hint

Calculate the code length for each character based on the Huffman tree and multiply by frequency in the string.

The Huffman codes assign shorter codes to more frequent characters. After building the tree, the codes lengths are: 'a':3 bits, 'b':3 bits, 'c':2 bits, 'd':1 bit. Encoding "abcd" uses 3 + 3 + 2 + 1 = 9 bits, but since the string is "abcd" (one of each), total bits = 3+3+2+1=9 bits. The correct answer is 9 bits.

🔧 Debug

advanced

Identify the Error in Huffman Tree Node Comparison

What error will occur when running this C# code snippet that uses a SortedSet to build a Huffman tree?

DSA C#

var pq = new SortedSet<Node>();
// Node class does not implement IComparable
pq.Add(new Node('a', 5));
pq.Add(new Node('b', 9));
var first = pq.Min;

A ArgumentNullException when adding nodes

B NullReferenceException at pq.Min

C InvalidOperationException: Failed to compare two elements in the array.

D No error, code runs successfully

💡 Hint

SortedSet requires elements to be comparable or a comparer to be provided.

SortedSet needs to compare elements to maintain order. Without IComparable or a comparer, it throws InvalidOperationException.

🚀 Application

advanced

Huffman Encoding Compression Ratio Calculation

A text contains 1000 characters with frequencies: {'x': 500, 'y': 300, 'z': 200}. Using Huffman encoding, the average bits per character is 1.5 bits. What is the compression ratio compared to using 8 bits per character fixed-length encoding?

A 18.75%

B 62.5%

C 81.25%

D 37.5%

💡 Hint

Compression ratio = (compressed size / original size) * 100%

Original size = 1000 * 8 = 8000 bits. Compressed size = 1000 * 1.5 = 1500 bits. Ratio = (1500 / 8000) * 100% = 18.75%. The question asks for compression ratio compared to fixed-length encoding, which is the percentage of original size used, so 18.75%.

❓ Predict Output

expert

Output of Huffman Encoding Map Generation

What is the output of the following C# code that generates Huffman codes for characters and prints the code for 'b'?

DSA C#

using System;
using System.Collections.Generic;

class Node {
    public char? Symbol;
    public int Frequency;
    public Node Left, Right;
    public Node(char? symbol, int freq) {
        Symbol = symbol;
        Frequency = freq;
        Left = Right = null;
    }
}

class Program {
    static void BuildCodes(Node node, string code, Dictionary<char, string> codes) {
        if (node == null) return;
        if (node.Symbol != null) {
            codes[node.Symbol.Value] = code;
            return;
        }
        BuildCodes(node.Left, code + "0", codes);
        BuildCodes(node.Right, code + "1", codes);
    }

    static void Main() {
        var frequencies = new Dictionary<char, int> {{'a', 1}, {'b', 1}, {'c', 2}, {'d', 4}};
        var pq = new SortedSet<(int freq, int id, Node node)>(Comparer<(int, int, Node)>.Create((x, y) => {
            int cmp = x.freq.CompareTo(y.freq);
            if (cmp == 0) return x.id.CompareTo(y.id);
            return cmp;
        }));
        int id = 0;
        foreach (var kvp in frequencies) {
            pq.Add((kvp.Value, id++, new Node(kvp.Key, kvp.Value)));
        }
        while (pq.Count > 1) {
            var first = pq.Min; pq.Remove(first);
            var second = pq.Min; pq.Remove(second);
            var merged = new Node(null, first.freq + second.freq);
            merged.Left = first.node;
            merged.Right = second.node;
            pq.Add((merged.Frequency, id++, merged));
        }
        var root = pq.Min.node;
        var codes = new Dictionary<char, string>();
        BuildCodes(root, "", codes);
        Console.WriteLine(codes['b']);
    }
}

A 01

B 00

C 10

D 11

💡 Hint

Trace the tree construction and code assignment carefully.

The Huffman tree merges 'a'(1) and 'b'(1) first, assigning 'a' code '00' and 'b' code '01'. Thus, 'b' code is '01'.

Practice

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

easy

A. To assign shorter codes to more frequent characters

B. To assign equal length codes to all characters

C. To encrypt data for security

D. To sort characters alphabetically

Solution

1. Step 1: Understand Huffman Encoding goal

   Huffman Encoding compresses data 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 purpose; others describe different concepts.

3. Final Answer:

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

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 compression with encryption
• Assuming sorting is the main goal

2. Which of the following C# code snippets correctly declares a priority queue for Huffman nodes using .NET 6+ syntax?

easy

A. var pq = new PriorityQueue();

B. PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();

C. var pq = new PriorityQueue<HuffmanNode>();

D. PriorityQueue pq = new PriorityQueue();

Solution

1. Step 1: Recall .NET 6+ PriorityQueue syntax

   The correct syntax requires two generic types: the element and its priority, e.g., PriorityQueue.

2. Step 2: Check each option

   var pq = new PriorityQueue(); uses correct syntax with element type HuffmanNode and priority int. Others have syntax errors or missing types.

3. Final Answer:

   var pq = new PriorityQueue<HuffmanNode, int>(); -> Option A

4. Quick Check:

   PriorityQueue<TElement, TPriority> = var pq = new PriorityQueue(); [OK]

Hint: PriorityQueue needs element and priority types in angle brackets [OK]

Common Mistakes:

• Omitting priority type in PriorityQueue declaration
• Using empty angle brackets <> without types
• Declaring without var or explicit type

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

medium

A. 110

B. 1100

C. 111

D. 10

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies: 5(a) and 9(b) -> 14; then 12(c) and 13(d) -> 25; finally 14 and 25 -> 39 root.

2. Step 2: Assign codes from root

   Left branch is '0', right is '1'. 'a' is in left subtree of 14, which is left subtree of root, so code is '1100'.

3. Final Answer:

   1100 -> Option B

4. Quick Check:

   Lowest freq 'a' gets longest code '1100' [OK]

Hint: Lowest freq chars get longer codes in Huffman [OK]

Common Mistakes:

• Assigning shorter codes to lowest frequency chars
• Mixing left/right branch codes
• Not building tree step-by-step

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

var pq = new PriorityQueue<HuffmanNode, int>();
pq.Enqueue(new HuffmanNode('a', 5), 5);
pq.Enqueue(new HuffmanNode('b', 9), 9);
var left = pq.Dequeue();
var right = pq.Dequeue();
var parent = new HuffmanNode(null, left.freq + right.freq);
pq.Enqueue(parent, parent.freq);

medium

A. PriorityQueue requires priority as first argument in Enqueue

B. Dequeue returns a tuple, not a HuffmanNode

C. Cannot use null for character in HuffmanNode

D. HuffmanNode constructor missing frequency parameter

Solution

1. Step 1: Recall PriorityQueue Dequeue return type

   In .NET PriorityQueue, Dequeue() returns the element (HuffmanNode) directly, not a tuple.

2. Step 2: Verify other code parts

   Enqueue(element, priority) order is correct. left.freq and right.freq access is valid assuming public freq property. Constructor called with two arguments consistently.

3. Step 3: Identify the error

   Cannot use null for character in HuffmanNode is correct: new HuffmanNode(null, ...) fails because the constructor expects a non-nullable char (inferred from leaf nodes like new HuffmanNode('a', 5)), and null cannot be assigned to char. Use char? for character field or '\0' for internal nodes.

4. Final Answer:

   Cannot use null for character in HuffmanNode -> Option C

5. Quick Check:

   char cannot be null; use char? for internal nodes [OK]

Hint: Cannot assign null to char; use char? for internal nodes [OK]

Common Mistakes:

• Assuming Dequeue returns tuple with priority
• Thinking Enqueue argument order is reversed
• Thinking null can be passed to non-nullable char constructor

5. You have characters with frequencies: {'x': 1, 'y': 1, 'z': 1, 'w': 1}. After building the Huffman tree, what is the minimum and maximum length of the Huffman codes assigned to these characters?

hard

A. Minimum length = 2, Maximum length = 3

B. Minimum length = 1, Maximum length = 3

C. Minimum length = 1, Maximum length = 2

D. Minimum length = 2, Maximum length = 2

Solution

1. Step 1: Build Huffman tree for equal frequencies

   All freq=1. Dequeue two leaves (1+1=2), now pq has two leaves(1) and one internal(2). Dequeue two leaves (1+1=2), now two internals(2+2=4 root). Perfectly balanced tree.

2. Step 2: Determine code lengths

   All four leaves at depth 2, so all codes length 2: min=2, max=2.

3. Final Answer:

   Minimum length = 2, Maximum length = 2 -> Option D

4. Quick Check:

   4 equal freq chars: balanced tree, all codes length 2 [OK]

Hint: Equal freq chars yield balanced tree, equal code lengths [OK]

Common Mistakes:

• Thinking tree unbalanced, max length=3
• Thinking minimum code length=1 for 4 chars
• Ignoring that equal freq forces balance