Huffman Encoding in DSA C# - Build from Scratch

Huffman Encoding

📖 Scenario: You are working on a text compression tool. Huffman encoding is a way to compress text by using shorter codes for common letters and longer codes for rare letters.We will build a simple Huffman encoding step-by-step to understand how it works.

🎯 Goal: Create a program that builds a Huffman tree from character frequencies and generates the Huffman codes for each character.

📋 What You'll Learn

Create a dictionary with character frequencies

Create a priority queue to hold nodes by frequency

Build the Huffman tree by combining lowest frequency nodes

Generate Huffman codes by traversing the tree

Print the Huffman codes for each character

💡 Why This Matters

🌍 Real World

Huffman encoding is used in file compression formats like ZIP and image formats like JPEG to reduce file size by encoding frequent data with fewer bits.

💼 Career

Understanding Huffman encoding helps in roles related to data compression, storage optimization, and efficient data transmission.

1

Create the character frequency dictionary

Create a dictionary called charFreq with these exact entries: 'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45.

DSA C#

# Create the dictionary charFreq with given character frequencies
# Your code here

Hint

Use Dictionary<char, int> and initialize it with the exact character-frequency pairs.

2

Create a priority queue of nodes

Create a class Node with public fields char Character, int Frequency, Node Left, and Node Right. Then create a PriorityQueue<Node, int> called pq and add a Node for each character in charFreq with its frequency as priority.

DSA C#

using System.Collections.Generic;

Dictionary charFreq = new Dictionary
{
    {'a', 5},
    {'b', 9},
    {'c', 12},
    {'d', 13},
    {'e', 16},
    {'f', 45}
};

// Define Node class and create PriorityQueue pq
// Your code here

Hint

Define the Node class with two constructors: one for leaf nodes and one for internal nodes. Use PriorityQueue<Node, int> to store nodes by frequency.

3

Build the Huffman tree

Use a while loop that runs while pq.Count > 1. Inside the loop, dequeue two nodes with lowest frequency, create a new parent Node combining them, and enqueue the parent node back into pq with its frequency as priority. Store the final node in root.

DSA C#

using System.Collections.Generic;

Dictionary charFreq = new Dictionary
{
    {'a', 5},
    {'b', 9},
    {'c', 12},
    {'d', 13},
    {'e', 16},
    {'f', 45}
};

public class Node
{
    public char Character;
    public int Frequency;
    public Node Left;
    public Node Right;

    public Node(char character, int frequency)
    {
        Character = character;
        Frequency = frequency;
        Left = null;
        Right = null;
    }

    public Node(Node left, Node right)
    {
        Character = '\0';
        Frequency = left.Frequency + right.Frequency;
        Left = left;
        Right = right;
    }
}

PriorityQueue pq = new PriorityQueue();
foreach (var kvp in charFreq)
{
    pq.Enqueue(new Node(kvp.Key, kvp.Value), kvp.Value);
}

// Build the Huffman tree and store the root node in variable root
// Your code here

Hint

Keep combining two smallest nodes until only one node remains. This node is the root of the Huffman tree.

4

Generate and print Huffman codes

Create a recursive method GenerateCodes that takes a Node, a string code, and a Dictionary<char, string> codes. If the node is a leaf (both children null), add the character and code to codes. Otherwise, call GenerateCodes on left child with code + "0" and right child with code + "1". Then call GenerateCodes with root, empty string, and an empty dictionary. Finally, print each character and its code in codes in the format char: code.

DSA C#

using System;
using System.Collections.Generic;

Dictionary charFreq = new Dictionary
{
    {'a', 5},
    {'b', 9},
    {'c', 12},
    {'d', 13},
    {'e', 16},
    {'f', 45}
};

public class Node
{
    public char Character;
    public int Frequency;
    public Node Left;
    public Node Right;

    public Node(char character, int frequency)
    {
        Character = character;
        Frequency = frequency;
        Left = null;
        Right = null;
    }

    public Node(Node left, Node right)
    {
        Character = '\0';
        Frequency = left.Frequency + right.Frequency;
        Left = left;
        Right = right;
    }
}

PriorityQueue pq = new PriorityQueue();
foreach (var kvp in charFreq)
{
    pq.Enqueue(new Node(kvp.Key, kvp.Value), kvp.Value);
}

Node root = null;
while (pq.Count > 1)
{
    Node left = pq.Dequeue();
    Node right = pq.Dequeue();
    Node parent = new Node(left, right);
    pq.Enqueue(parent, parent.Frequency);
}
root = pq.Dequeue();

// Define GenerateCodes method and print the Huffman codes
// Your code here

Hint

Traverse the tree recursively. Assign '0' for left edges and '1' for right edges. Print each character and its code.

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