Huffman Encoding in DSA C - Execution Trace

Concept Flow - Huffman Encoding

Count frequency of each char

↓

Create leaf nodes for each char

↓

Build min-heap of leaf nodes

↓

While more than one node in heap

↓

Extract two smallest nodes

↓

Create new internal node with sum freq

↓

Insert new node back to heap

↓

Heap has one node -> root of Huffman tree

↓

Traverse tree to assign codes

↓

Encode input using codes

The flow shows counting frequencies, building a min-heap, merging nodes to build the tree, then assigning codes.

Execution Sample

DSA C

char input[] = "abbccc";
// Frequencies: a=1, b=2, c=3
// Build tree and assign codes
// a: 10, b: 11, c: 0
// Encode input

This code counts frequencies of characters, builds Huffman tree, assigns codes, and encodes the input string.

Execution Table

Step	Action	Heap Content (freq:char)	New Node Created	Heap After Insertion	Notes
1	Count frequencies	-	-	-	a=1, b=2, c=3
2	Create leaf nodes	1:a, 2:b, 3:c	-	-	Leaf nodes created for each char
3	Build min-heap	1:a, 2:b, 3:c	-	-	Min-heap built with leaf nodes
4	Extract two smallest	1:a, 2:b, 3:c	-	-	Extracted 1:a and 2:b
5	Create internal node	-	3:internal	-	New node freq=1+2=3
6	Insert new node	3:c, 3:internal	-	3:c, 3:internal	Heap now has two nodes with freq=3
7	Extract two smallest	3:c, 3:internal	-	-	Extracted 3:c and 3:internal
8	Create internal node	-	6:root	-	New node freq=3+3=6 root
9	Insert new node	6:root	-	6:root	Heap has one node, tree complete
10	Assign codes	-	-	-	c=0, a=10, b=11
11	Encode input	-	-	-	Input 'abbccc' encoded as 10 11 11 0 0 0
12	End	-	-	-	Encoding complete

💡 Heap reduced to one node, Huffman tree built and encoding done

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	Final
freq_a	0	1	1	1	1
freq_b	0	2	2	2	2
freq_c	0	3	3	3	3
heap	empty	1:a,2:b,3:c	3:c,3:internal	6:root	6:root
codes	empty	empty	empty	c=0,a=10,b=11	c=0,a=10,b=11
encoded_string	empty	empty	empty	empty	10 11 11 0 0 0

Key Moments - 3 Insights

Why do we combine the two smallest frequency nodes first?

Combining smallest nodes first ensures the tree has minimal weighted path length, as shown in steps 4-8 where nodes with freq 1 and 2 are combined before others.

How do we know when the Huffman tree is complete?

When the heap has only one node left (step 9), that node is the root of the Huffman tree, so the tree is complete.

Why does character 'c' get the shortest code '0'?

Because 'c' has the highest frequency (3), it is placed closer to the root, resulting in a shorter code, as assigned in step 10.

Visual Quiz - 3 Questions

Look at the execution table at step 5, what is the frequency of the new internal node created?

A 3

B 2

C 1

D 6

💡 Hint

Check the 'New Node Created' column at step 5 in the execution_table.

At which step does the heap reduce to a single node?

A Step 6

B Step 9

C Step 4

D Step 11

💡 Hint

Look at the 'Heap After Insertion' column and the notes in the execution_table.

According to the variable_tracker, what is the encoded string after the final step?

A "10 11 11 0 0 0"

B "0 10 11 11 0 0"

C "11 10 0 0 0 11"

D "0 0 0 10 11 11"

💡 Hint

Check the 'encoded_string' row in the variable_tracker at the 'Final' column.

Concept Snapshot

Huffman Encoding builds a binary tree based on character frequencies.
1. Count frequencies.
2. Create leaf nodes and build a min-heap.
3. Merge two smallest nodes repeatedly until one node remains.
4. Assign codes by traversing the tree (left=0, right=1).
5. Encode input using these codes for compression.

Full Transcript

Huffman Encoding starts by counting how often each character appears. Then, each character becomes a leaf node with its frequency. These nodes go into a min-heap to always pick the smallest frequencies. We repeatedly take two smallest nodes, merge them into a new node with combined frequency, and put it back. When only one node remains, it is the root of the Huffman tree. We assign codes by going left (0) or right (1) in the tree. Characters with higher frequency get shorter codes. Finally, we encode the input string using these codes. This process compresses data efficiently.

Practice

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

easy

A. To assign equal length codes to all characters

B. To assign shorter codes to more frequent characters

C. To encrypt data for security

D. To sort characters alphabetically

Solution

1. Step 1: Understand Huffman Encoding purpose

   Huffman Encoding compresses data by giving shorter codes to characters that appear more often.

2. Step 2: Compare options with this purpose

   Only To assign shorter codes to more frequent characters matches this goal; others describe different concepts.

3. Final Answer:

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

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 data structure is primarily used to build the Huffman tree?

easy

A. Priority Queue (Min-Heap)

B. Stack

C. Queue

D. Hash Table

Solution

1. Step 1: Identify data structure for selecting smallest frequencies

   Huffman tree construction repeatedly picks two smallest frequency nodes.

2. Step 2: Match with data structure that supports this

   Priority Queue (Min-Heap) efficiently provides smallest elements first.

3. Final Answer:

   Priority Queue (Min-Heap) -> Option A

4. Quick Check:

   Smallest freq nodes from Min-Heap [OK]

Hint: Huffman uses Min-Heap to pick smallest frequencies fast [OK]

Common Mistakes:

• Choosing Stack or Queue which don't sort by frequency
• Confusing Hash Table with frequency sorting
• Ignoring the need for smallest frequency extraction

3. What is the output Huffman code for characters with frequencies: A=5, B=9, C=12, D=13, E=16, F=45?

Assuming standard Huffman tree construction, what is the code for character 'F'?

medium

A. 0

B. 10

C. 110

D. 111

Solution

1. Step 1: Build Huffman tree with given frequencies

   Combine smallest pairs: (A=5,B=9)=14, (C=12,D=13)=25, then combine 14 and 16 (E) = 30, then 25 and 30 = 55, finally combine 45 (F) and 55 = 100.

2. Step 2: Assign codes from root; 'F' is combined last and placed on left branch

   Since 'F' has highest frequency, it gets the shortest code '0'.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   Highest freq char gets shortest code '0' [OK]

Hint: Highest frequency char gets code '0' in Huffman [OK]

Common Mistakes:

• Assigning longer codes to highest frequency character
• Mixing up left/right branch codes
• Not building tree step-by-step

4. Consider this C code snippet for building a Huffman tree:

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

// Function to create a new node
struct Node* newNode(char data, int freq) {
  struct Node* temp = malloc(sizeof(struct Node));
  temp->data = data;
  temp->freq = freq;
  temp->left = temp->right = NULL;
  return temp;
}

// Code to combine two nodes
struct Node* combineNodes(struct Node* left, struct Node* right) {
  struct Node* parent = newNode('$', left->freq + right->freq);
  parent->left = left;
  parent->right = right;
  return parent;
}

// Usage:
struct Node* n1 = newNode('A', 5);
struct Node* n2 = newNode('B', 9);
struct Node* parent = combineNodes(n1, n2);

printf("Parent freq: %d\n", parent->freq);

What is the output of this code?

medium

A. Parent freq: 5

B. Parent freq: 9

C. Compilation error

D. Parent freq: 14

Solution

1. Step 1: Understand node creation and combination

   n1 has freq 5, n2 has freq 9; combineNodes sums frequencies: 5 + 9 = 14.

2. Step 2: Print parent frequency

   parent->freq is 14, so printf outputs "Parent freq: 14".

3. Final Answer:

   Parent freq: 14 -> Option D

4. Quick Check:

   5 + 9 = 14 frequency sum [OK]

Hint: Sum frequencies when combining nodes for parent freq [OK]

Common Mistakes:

• Printing child node frequency instead of parent
• Forgetting to sum frequencies
• Assuming compilation error due to struct usage

5. You have characters with frequencies: X=3, Y=3, Z=3, W=3. Using Huffman Encoding, what is the minimum total number of bits needed to encode the string "XYZWXYZW" (8 characters)?

hard

A. 12 bits

B. 24 bits

C. 16 bits

D. 8 bits

Solution

1. Step 1: Build Huffman tree for equal frequencies

   All characters have equal frequency (3), so Huffman codes will have equal length, typically 2 bits each (since 4 chars need 2 bits minimum).

2. Step 2: Calculate total bits for 8 characters

   Each character uses 2 bits, total bits = 8 * 2 = 16 bits.

3. Step 3: Re-examine options and problem

   Options include 16 and 24 bits. Since each char is 2 bits, total is 16 bits, but 24 bits is 24 bits. The string length is 8, so 8*2=16 bits is correct.

4. Final Answer:

   16 bits -> Option C

5. Quick Check:

   4 chars need 2 bits each, 8 chars total = 16 bits [OK]

Hint: Equal freq chars get equal length codes; multiply length by count [OK]

Common Mistakes:

• Assuming 1 bit per char incorrectly
• Multiplying frequency instead of code length
• Choosing 24 bits thinking 3 bits per char