Huffman Encoding in DSA C#

Mental Model

Huffman Encoding builds a tree to assign shorter codes to frequent letters and longer codes to rare letters, saving space.

Analogy: Imagine packing a suitcase where you put small, often-used items in easy-to-reach spots and big, rarely-used items deeper inside to save space.

Frequency Table:
A:5  B:9  C:12  D:13  E:16  F:45

Huffman Tree (partial):
        [100]
       /     \
    [45:F]   [55]
            /    \
         [25]    [30]
         /  \    /  \
     [12:C][13:D][14] [16:E]
                   /  \
                [5:A][9:B]

Dry Run Walkthrough

Input: string: "ABBCCCDDDDEEEEEFFFFFFF" (characters with frequencies: A=1, B=2, C=3, D=4, E=5, F=7)

Goal: Build Huffman tree and generate prefix codes for each character to minimize total bits used

Step 1: Create leaf nodes for each character with their frequencies

[A:1], [B:2], [C:3], [D:4], [E:5], [F:7]

Why: We start with all characters as separate nodes to build the tree

Step 2: Pick two nodes with smallest frequencies (A:1 and B:2), merge into new node with freq=3

[C:3], [D:4], [E:5], [F:7], [AB:3]

Why: Combine smallest frequencies to build tree bottom-up

Step 3: Pick two smallest nodes (C:3 and AB:3), merge into new node freq=6

[D:4], [E:5], [F:7], [CAB:6]

Why: Continue merging smallest nodes to build tree

Step 4: Pick two smallest nodes (D:4 and E:5), merge into new node freq=9

[F:7], [CAB:6], [DE:9]

Why: Keep merging until one node remains

Step 5: Pick two smallest nodes (F:7 and CAB:6), merge into new node freq=13

[DE:9], [FCAB:13]

Why: Merge next smallest nodes

Step 6: Merge last two nodes (DE:9 and FCAB:13) into root node freq=22

[ROOT:22]

Why: Final merge completes the Huffman tree

Step 7: Assign codes by traversing tree: left edge adds '0', right edge adds '1'

Codes: A=110, B=111, C=10, D=00, E=01, F=1

Why: Assign prefix codes so no code is prefix of another

Result:

Final Huffman Codes:
A:110
B:111
C:10
D:00
E:01
F:1

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class HuffmanNode : IComparable<HuffmanNode>
{
    public char? Character;
    public int Frequency;
    public HuffmanNode Left, Right;

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

    public int CompareTo(HuffmanNode other)
    {
        return Frequency - other.Frequency;
    }
}

class HuffmanEncoding
{
    public static HuffmanNode BuildTree(Dictionary<char, int> freq)
    {
        var pq = new SortedSet<HuffmanNode>(Comparer<HuffmanNode>.Create((a, b) =>
        {
            int cmp = a.Frequency.CompareTo(b.Frequency);
            if (cmp == 0)
            {
                if (a.Character == null && b.Character == null) return 1;
                if (a.Character == null) return 1;
                if (b.Character == null) return -1;
                return a.Character.Value.CompareTo(b.Character.Value);
            }
            return cmp;
        }));

        foreach (var kvp in freq)
        {
            pq.Add(new HuffmanNode(kvp.Key, kvp.Value));
        }

        while (pq.Count > 1)
        {
            var left = pq.Min; pq.Remove(left); // smallest freq
            var right = pq.Min; pq.Remove(right); // next smallest

            var merged = new HuffmanNode(null, left.Frequency + right.Frequency);
            merged.Left = left;
            merged.Right = right;

            pq.Add(merged);
        }

        return pq.Min; // root
    }

    public static void GenerateCodes(HuffmanNode root, string code, Dictionary<char, string> codes)
    {
        if (root == null) return;

        if (root.Character != null)
        {
            codes[root.Character.Value] = code == "" ? "0" : code;
            return;
        }

        GenerateCodes(root.Left, code + "0", codes); // left edge adds '0'
        GenerateCodes(root.Right, code + "1", codes); // right edge adds '1'
    }

    static void Main()
    {
        string input = "ABBCCCDDDDEEEEEFFFFFFF";
        var freq = new Dictionary<char, int>();
        foreach (char c in input)
        {
            freq[c] = freq.GetValueOrDefault(c, 0) + 1;
        }

        var root = BuildTree(freq);
        var codes = new Dictionary<char, string>();
        GenerateCodes(root, "", codes);

        foreach (var kvp in codes)
        {
            Console.WriteLine($"{kvp.Key}: {kvp.Value}");
        }
    }
}

var left = pq.Min; pq.Remove(left); // smallest freq

extract smallest frequency node to merge

var right = pq.Min; pq.Remove(right); // next smallest

extract next smallest frequency node to merge

var merged = new HuffmanNode(null, left.Frequency + right.Frequency);

create new internal node with combined frequency

merged.Left = left; merged.Right = right;

assign children to merged node to build tree

GenerateCodes(root.Left, code + "0", codes); // left edge adds '0'

assign '0' for left branch in code

GenerateCodes(root.Right, code + "1", codes); // right edge adds '1'

assign '1' for right branch in code

Output

A: 110

B: 111

C: 10

D: 00

E: 01

F: 1

Complexity Analysis

Time: O(n log n) because we insert and remove nodes from a priority structure n times

Space: O(n) because we store all nodes and codes for n unique characters

vs Alternative: Compared to fixed-length encoding which uses same bits per char, Huffman reduces average bits by assigning shorter codes to frequent chars

Edge Cases

Input string with only one unique character

Tree has single node; code assigned is empty string or '0' to represent that character

DSA C#

if (root.Character != null) { codes[root.Character.Value] = code == "" ? "0" : code; return; }

Input string is empty

No tree built; no codes generated; program outputs nothing

DSA C#

foreach (var kvp in freq) { ... } handles empty dictionary gracefully

Multiple characters with same frequency

SortedSet comparator handles tie by character order to keep deterministic tree

DSA C#

Comparer lambda in SortedSet constructor

When to Use This Pattern

When you need to compress data by assigning variable-length codes based on frequency, reach for Huffman Encoding because it builds an optimal prefix code tree.

Common Mistakes

Mistake: Not handling tie frequencies properly causing unstable tree and inconsistent codes
Fix: Use a tie-breaker in priority queue comparator to ensure deterministic order

Mistake: Assigning codes only at leaves without checking for single-node tree
Fix: Add condition to assign code even if tree has only one node

Summary

Builds a tree to assign shorter binary codes to frequent characters for efficient compression.

Use when you want to compress data by encoding characters with variable-length prefix codes.

The key insight is merging lowest frequency nodes first to build an optimal prefix code tree.

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