Huffman Encoding in DSA Typescript - Execution Trace

Concept Flow - Huffman Encoding

Count frequency of each character

↓

Create leaf nodes for each char

↓

Build min-heap from leaf nodes

↓

While heap size > 1

↓

Extract two smallest nodes

↓

Create new internal node with these two as children

↓

Insert new node back into heap

Back to While↓

Heap has one node: root of Huffman Tree

↓

Traverse tree to assign codes

↓

Output codes for each character

↩Back to While

This flow shows how Huffman Encoding builds a tree from character frequencies, then assigns binary codes by traversing the tree.

Execution Sample

DSA Typescript

const freq = {a:5, b:9, c:12, d:13, e:16, f:45};
// Build Huffman Tree and assign codes
// Output codes for each character

This code builds a Huffman tree from given character frequencies and outputs the binary codes.

Execution Table

Step	Heap Content (nodes with freq)	Action	New Node Created	Heap After Insertion
1	[a:5, b:9, c:12, d:13, e:16, f:45]	Extract two smallest: a:5, b:9	Node(ab):14	[Node(ab):14, c:12, d:13, e:16, f:45]
2	[Node(ab):14, c:12, d:13, e:16, f:45]	Extract two smallest: c:12, d:13	Node(cd):25	[Node(ab):14, Node(cd):25, e:16, f:45]
3	[Node(ab):14, Node(cd):25, e:16, f:45]	Extract two smallest: Node(ab):14, e:16	Node(abe):30	[Node(cd):25, Node(abe):30, f:45]
4	[Node(cd):25, Node(abe):30, f:45]	Extract two smallest: Node(cd):25, Node(abe):30	Node(cdabe):55	[f:45, Node(cdabe):55]
5	[f:45, Node(cdabe):55]	Extract two smallest: f:45, Node(cdabe):55	Node(root):100	[Node(root):100]
6	[Node(root):100]	Only one node left, stop	-	[Node(root):100]

💡 Heap size is 1, Huffman tree is complete with root node frequency 100

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
Heap	[a:5, b:9, c:12, d:13, e:16, f:45]	[Node(ab):14, c:12, d:13, e:16, f:45]	[Node(ab):14, Node(cd):25, e:16, f:45]	[Node(cd):25, Node(abe):30, f:45]	[f:45, Node(cdabe):55]	[Node(root):100]	[Node(root):100]
New Node	-	Node(ab):14	Node(cd):25	Node(abe):30	Node(cdabe):55	Node(root):100	-

Key Moments - 3 Insights

Why do we always pick the two smallest frequency nodes from the heap?

Picking the two smallest nodes ensures the tree has minimal weighted path length, which leads to optimal prefix codes. See execution_table steps 1-5 where smallest nodes are combined each time.

What happens when the heap size becomes 1?

When heap size is 1, it means the Huffman tree is fully built with a single root node. This is shown in execution_table step 6 where the process stops.

Why do we insert the new combined node back into the heap?

Inserting the new node back keeps the heap updated with combined frequencies so the next smallest pairs can be extracted. This is shown in execution_table after each new node creation.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what nodes are extracted from the heap?

A Node(ab):14 and e:16

B c:12 and d:13

C a:5 and b:9

D f:45 and Node(cdab e):55

💡 Hint

Check the 'Action' column at Step 3 in execution_table

At which step does the heap size become 1, ending the tree building?

A Step 4

B Step 5

C Step 6

D Step 3

💡 Hint

Look at the 'Exit Note' and Step 6 in execution_table

If the frequency of 'f' was smaller than 'e', how would the heap content change after Step 4?

A Node(abe):30 would be replaced by Node(abf)

B Node(cd):25 would be replaced by Node(cf)

C Node(cdab e):55 would have a smaller frequency

D Heap would contain f:45 and Node(cdab e):55 as before

💡 Hint

Consider how combining smallest nodes changes new node frequencies in variable_tracker

Concept Snapshot

Huffman Encoding builds a binary tree from character frequencies.
Use a min-heap to repeatedly combine two smallest nodes.
Each combined node frequency is sum of children.
Stop when one node remains: the root.
Traverse tree to assign binary codes (left=0, right=1).
Codes are prefix-free and optimal for compression.

Full Transcript

Huffman Encoding starts by counting how often each character appears. Then, it creates leaf nodes for each character with their frequencies. These nodes go into a min-heap. We repeatedly take out the two smallest nodes, combine them into a new node with frequency equal to their sum, and put this new node back into the heap. This continues until only one node remains, which is the root of the Huffman tree. Finally, we traverse the tree to assign binary codes to each character, where going left adds '0' and right adds '1'. This method produces the shortest possible codes for the characters based on their frequencies.

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 bits used by giving shorter codes to frequent characters.

2. Step 2: Compare options with this goal

   Only To assign shorter codes to more frequent characters matches this goal. Others describe different or incorrect purposes.

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 in Huffman [OK]

Common Mistakes:

• Thinking Huffman assigns equal length codes
• Confusing Huffman with encryption
• Assuming it sorts characters alphabetically

2. Which TypeScript data structure is best suited to build the priority queue for Huffman Encoding?

easy

A. Array with manual sorting

B. Min-Heap

C. Set

D. Map

Solution

1. Step 1: Identify priority queue needs

   Huffman Encoding requires repeatedly extracting the smallest frequency node efficiently.

2. Step 2: Choose data structure for efficient min extraction

   Min-Heap allows quick access and removal of the smallest element, ideal for this use.

3. Final Answer:

   Min-Heap -> Option B

4. Quick Check:

   Priority queue = Min-Heap for Huffman [OK]

Hint: Use Min-Heap for efficient smallest element extraction [OK]

Common Mistakes:

• Using Set which has no order
• Using Map which is key-value, not priority queue
• Using Array without sorting is inefficient

3. What is the output Huffman code for characters {a:5, b:9, c:12, d:13, e:16, f:45} after building the Huffman tree?

medium

A. { 'f': '1', 'c': '00', 'd': '01', 'a': '100', 'b': '101', 'e': '110' }

B. { 'a': '0', 'b': '10', 'c': '110', 'd': '1110', 'e': '1111', 'f': '101' }

C. { 'f': '0', 'c': '100', 'd': '101', 'a': '1100', 'b': '1101', 'e': '111' }

D. { 'a': '111', 'b': '110', 'c': '10', 'd': '0', 'e': '101', 'f': '100' }

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies stepwise: (a=5,b=9)->14, (c=12,d=13)->25, then combine 14 and 16 (e) and so on, finally f=45 is highest frequency with shortest code.

2. Step 2: Assign codes from tree paths

   Left edges as '0', right edges as '1' produce codes: f='0', c='100', d='101', a='1100', b='1101', e='111'.

3. Final Answer:

   { 'f': '0', 'c': '100', 'd': '101', 'a': '1100', 'b': '1101', 'e': '111' } -> Option C

4. Quick Check:

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

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

Common Mistakes:

• Assigning codes without building tree
• Mixing left/right edge bits
• Ignoring frequency order

4. Given this TypeScript snippet for Huffman tree node insertion, what is the bug?

class Node {
  constructor(public char: string | null, public freq: number, public left: Node | null = null, public right: Node | null = null) {}
}

function insertNode(queue: Node[], node: Node) {
  queue.push(node);
  queue.sort((a, b) => a.freq - b.freq);
}

// Usage
const queue: Node[] = [];
insertNode(queue, new Node('a', 5));
insertNode(queue, new Node('b', 9));
insertNode(queue, new Node(null, 14));

medium

A. Sorting after push is inefficient; use a Min-Heap instead

B. Node constructor missing type annotations

C. Function insertNode should remove duplicates

D. queue.sort comparator should be reversed

Solution

1. Step 1: Analyze insertNode function

   It pushes a node then sorts the entire queue array by frequency each time.

2. Step 2: Identify inefficiency

   Sorting the whole array on every insertion is inefficient for large data; a Min-Heap is better for priority queue operations.

3. Final Answer:

   Sorting after push is inefficient; use a Min-Heap instead -> Option A

4. Quick Check:

   Priority queue needs efficient insert and extract [OK]

Hint: Use Min-Heap, not array sort, for priority queue [OK]

Common Mistakes:

• Thinking sorting order is wrong
• Missing inefficiency of sorting whole array
• Confusing type annotations as bug

5. You have a string "aaabbc" and want to encode it using Huffman Encoding. Which of the following is the correct Huffman code assignment and encoded bit string?

hard

A. Codes: {a:'0', b:'10', c:'11'}, Encoded: '000101011'

B. Codes: {a:'10', b:'0', c:'11'}, Encoded: '101010011'

C. Codes: {a:'0', b:'11', c:'10'}, Encoded: '00011110'

D. Codes: {a:'1', b:'0', c:'10'}, Encoded: '1110010'

Solution

1. Step 1: Calculate frequencies

   String "aaabbc" has frequencies: a=3, b=2, c=1.

2. Step 2: Build Huffman tree and assign codes

   Lowest freq c=1 and b=2 combine first, then with a=3. Assign codes: a='0', b='10', c='11'.

3. Step 3: Encode string using codes

   Encoding "aaabbc" = a(3 times) '0 0 0', b(2 times) '10 10', c(1 time) '11' -> '000101011'.

4. Final Answer:

   Codes: {a:'0', b:'10', c:'11'}, Encoded: '000101011' -> Option A

5. Quick Check:

   Freq order a>b>c matches codes and encoding [OK]

Hint: Encode by replacing chars with shortest codes from tree [OK]

Common Mistakes:

• Mixing code assignments
• Encoding with wrong code bits
• Ignoring frequency order in code assignment