Huffman Encoding in DSA Javascript - Execution Trace

Concept Flow - Huffman Encoding

Count frequencies of chars

↓

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

↓

Insert new node back to heap

↓

Heap size == 1 -> Root node

↓

Traverse tree to assign codes

↓

Return char-to-code map

The flow counts character frequencies, builds a tree by combining smallest nodes, then assigns codes by traversing the tree.

Execution Sample

DSA Javascript

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

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

Execution Table

Step	Heap Content (nodes with freq)	Action	New Node Created (freq)	Heap After Insertion
1	[a:5, b:9, c:12, d:13, e:16, f:45]	Extract two smallest: a(5), b(9)	Node(14)	[c:12, d:13, e:16, f:45, 14]
2	[c:12, d:13, e:16, f:45, 14]	Extract two smallest: c(12), d(13)	Node(25)	[e:16, f:45, 14, 25]
3	[e:16, f:45, 14, 25]	Extract two smallest: 14, e(16)	Node(30)	[f:45, 25, 30]
4	[f:45, 25, 30]	Extract two smallest: 25, 30	Node(55)	[f:45, 55]
5	[f:45, 55]	Extract two smallest: f(45), 55	Node(100)	[100]
6	[100]	Heap size 1, root node ready	-	[100]
7	[100]	Traverse tree to assign codes	-	-

💡 Heap size is 1, tree construction complete, ready for code assignment

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]	[c:12, d:13, e:16, f:45, 14]	[e:16, f:45, 14, 25]	[f:45, 25, 30]	[f:45, 55]	[100]	[100]
New Node	-	14 (a+b)	25 (c+d)	30 (14+e)	55 (25+30)	100 (f+55)	-
Codes	-	-	-	-	-	-	{f: '0', c: '100', d: '101', a: '1100', b: '1101', e: '111'}

Key Moments - 3 Insights

Why do we combine the two smallest frequency nodes each time?

Combining the 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 extracted and combined.

What does the final single node in the heap represent?

The final node is the root of the Huffman tree containing all characters. This is shown in execution_table step 6 where heap size is 1, meaning tree construction is complete.

How are the binary codes assigned after building the tree?

Codes are assigned by traversing the tree: going left adds '0', right adds '1'. This is summarized in execution_table step 7 and variable_tracker final codes.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, which nodes were combined to create the new node?

A Nodes with frequencies 25 and 30

B Nodes with frequencies 12 and 13

C Nodes with frequencies 14 and 16

D Nodes with frequencies 5 and 9

💡 Hint

Check the 'Action' and 'New Node Created' columns at Step 3 in execution_table

At which step does the heap size become 1, indicating the tree is complete?

A Step 5

B Step 6

C Step 4

D Step 7

💡 Hint

Look at the 'Heap Content' and 'Action' columns in execution_table for when heap size is 1

According to variable_tracker, what is the code assigned to character 'f'?

A '0'

B '1100'

C '1'

D '111'

💡 Hint

Check the 'Codes' row in variable_tracker under 'Final' column

Concept Snapshot

Huffman Encoding builds a binary tree from character frequencies.
Combine two smallest nodes repeatedly to form new nodes.
Final single node is the root of the tree.
Traverse tree left=0, right=1 to assign codes.
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 frequency. These nodes go into a min-heap. We repeatedly take out the two smallest nodes, combine them into a new node with their summed frequency, and put this new node back into the heap. When only one node remains, it is the root of the Huffman tree. Finally, we assign binary codes by traversing the tree: going left adds '0' and right adds '1'. This process creates efficient, prefix-free codes for each character.

Practice

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

easy

A. To encrypt data for security

B. To assign shorter codes to more frequent characters

C. To assign equal length codes to all characters

D. To sort characters alphabetically

Solution

1. Step 1: Understand Huffman Encoding purpose

   Huffman Encoding compresses data by using shorter codes for frequent characters and longer codes for less frequent ones.

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 alphabetical sorting is the goal

2. Which of the following is the correct way to represent a node in a Huffman tree in JavaScript?

easy

A. const node = 'a:5';

B. const node = [ 'a', 5, null, null ];

C. const node = function(char, freq) { this.char = char; this.freq = freq; };

D. const node = { char: 'a', freq: 5, left: null, right: null };

Solution

1. Step 1: Identify proper node structure for Huffman tree

   A node should store character, frequency, and pointers to left and right children.

2. Step 2: Check each option

   const node = { char: 'a', freq: 5, left: null, right: null }; uses an object with char, freq, left, right properties which is clear and correct. const node = [ 'a', 5, null, null ]; uses an array without labels, making it unclear. const node = function(char, freq) { this.char = char; this.freq = freq; }; is a constructor but incomplete (no left/right). const node = 'a:5'; is a string, not a node.

3. Final Answer:

   const node = { char: 'a', freq: 5, left: null, right: null }; -> Option D

4. Quick Check:

   Node = object with char, freq, left, right [OK]

Hint: Use objects with named properties for tree nodes [OK]

Common Mistakes:

• Using arrays without labels for nodes
• Using strings instead of objects
• Missing left and right child pointers

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

medium

A. 00

B. 111

C. 110

D. 10

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies: 5('a') and 9('b') -> node with freq 14. Then combine 12('c') and 13('d') -> node with freq 25. Finally combine 14 and 25 -> root 39.

2. Step 2: Assign codes by traversing tree

   Left edges get '0', right edges get '1'. 'a' is left child of first combined node, so code is '110'.

3. Final Answer:

   110 -> Option C

4. Quick Check:

   Lowest freq char 'a' gets code '110' [OK]

Hint: Combine lowest freq nodes first, assign 0 to left [OK]

Common Mistakes:

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

4. Consider this JavaScript snippet for building a Huffman tree:

function buildTree(freqMap) {
  let nodes = Object.entries(freqMap).map(([char, freq]) => ({char, freq}));
  while(nodes.length > 1) {
    nodes.sort((a,b) => a.freq - b.freq);
    let left = nodes.shift();
    let right = nodes.shift();
    let newNode = {char: null, freq: left.freq + right.freq, left, right};
    nodes.push(newNode);
  }
  return nodes[0];
}

What is the bug in this code?

medium

A. The function does not handle empty freqMap

B. The newNode should not have char property

C. The nodes array is not updated correctly after push

D. The nodes array is not sorted before each iteration

Solution

1. Step 1: Analyze function behavior with empty input

   If freqMap is empty, Object.entries(freqMap) is empty array, so nodes is empty. The while loop condition nodes.length > 1 is false, so function returns nodes[0], which is undefined.

2. Step 2: Identify missing edge case handling

   The function does not check for empty freqMap and returns undefined instead of a valid tree or null.

3. Final Answer:

   The function does not handle empty freqMap -> Option A

4. Quick Check:

   Empty input returns undefined, missing edge case [OK]

Hint: Check empty input cases in tree-building functions [OK]

Common Mistakes:

• Assuming nodes always have elements
• Ignoring empty input edge cases
• Thinking sorting is missing when it is present

5. You have the string "abbcccdddd". Using Huffman Encoding, what is the minimum total number of bits needed to encode this string? Frequencies: a=1, b=2, c=3, d=4.

hard

A. 19 bits

B. 17 bits

C. 15 bits

D. 21 bits

Solution

1. Step 1: Build Huffman tree and assign codes

   Frequencies: a=1, b=2, c=3, d=4. Combine a(1) and b(2) -> node(3). Combine node(3) and c(3) -> node(6). Combine node(6) and d(4) -> root(10). Assign codes: d=0 (1 bit), c=10 (2 bits), b=110 (3 bits), a=111 (3 bits).

2. Step 2: Calculate total bits

   Total bits = (a:1*3) + (b:2*3) + (c:3*2) + (d:4*1) = 3 + 6 + 6 + 4 = 19 bits.

3. Final Answer:

   19 bits -> Option A

4. Quick Check:

   Sum(freq * code length) = 19 bits [OK]

Hint: Multiply frequency by code length, then sum all [OK]

Common Mistakes:

• Adding frequencies instead of weighted bits
• Assigning wrong code lengths
• Ignoring frequency when calculating total bits