Huffman Encoding in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is Huffman Encoding?

Huffman Encoding is a way to compress data by using shorter codes for common characters and longer codes for rare ones. It builds a tree to assign these codes based on character frequency.

beginner

What data structure is mainly used in Huffman Encoding?

A binary tree called the Huffman Tree is used. It helps assign unique binary codes to characters based on their frequency.

intermediate

How does Huffman Encoding assign codes to characters?

Characters with higher frequency get shorter codes, and characters with lower frequency get longer codes. Codes are assigned by traversing the Huffman Tree from root to leaves.

beginner

Why is Huffman Encoding considered a lossless compression method?

Because it allows the original data to be perfectly reconstructed from the encoded data without losing any information.

beginner

What is the first step in building a Huffman Tree?

Count the frequency of each character in the input data and create a leaf node for each character with its frequency.

What does Huffman Encoding use to decide the length of each character's code?

A Random assignment

B Character frequency

C Character ASCII value

D Alphabetical order

Huffman Encoding assigns shorter codes to characters that appear more frequently.

Which data structure is essential for building the Huffman Tree?

A Priority Queue

B Queue

C Stack

D Hash Table

A priority queue is used to always pick the two nodes with the smallest frequencies to build the tree.

What kind of tree is the Huffman Tree?

A Binary Search Tree

B AVL Tree

C Binary Tree

D Trie

The Huffman Tree is a binary tree used for encoding characters.

What is the main goal of Huffman Encoding?

A Search data

B Encrypt data

C Sort data

D Compress data

Huffman Encoding compresses data by reducing the total number of bits needed.

How do you decode a Huffman encoded string?

A By using the Huffman Tree to map codes back to characters

B By reversing the string

C By counting character frequencies again

D By using ASCII values

Decoding uses the Huffman Tree to translate binary codes back to original characters.

Explain the process of building a Huffman Tree from a given string.

Think about how you pick and combine nodes based on frequency.

Describe how Huffman Encoding compresses data and why it is efficient.

Focus on code length and frequency relationship.

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