Huffman Encoding in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Huffman Encoding Tree Construction

What is the output of the following code that builds a Huffman tree and prints the root node's frequency?

DSA Javascript

class Node {
  constructor(char, freq, left = null, right = null) {
    this.char = char;
    this.freq = freq;
    this.left = left;
    this.right = right;
  }
}

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

const freqMap = { a: 5, b: 9, c: 12, d: 13, e: 16, f: 45 };
const root = buildHuffmanTree(freqMap);
console.log(root.freq);

A 50

B 45

C 100

D 60

💡 Hint

Sum all frequencies to find the root node frequency.

The root node frequency is the sum of all character frequencies because the Huffman tree merges all nodes into one. Adding 5 + 9 + 12 + 13 + 16 + 45 equals 100.

🧠 Conceptual

intermediate

Understanding Huffman Encoding Output Length

Given the frequencies {a: 3, b: 2, c: 1}, what is the length of the encoded string for the input "abac" using Huffman encoding?

A 8 bits

B 7 bits

C 6 bits

D 5 bits

💡 Hint

Assign shorter codes to more frequent characters and count bits for each character in the string.

Huffman codes might be: a=0, b=10, c=11. Encoding "abac" is 0 (a) + 10 (b) + 0 (a) + 11 (c) = 7 bits total.

🔧 Debug

advanced

Identify the Error in Huffman Tree Node Comparison

What error will the following code produce when building a Huffman tree?

DSA Javascript

class Node {
  constructor(char, freq) {
    this.char = char;
    this.freq = freq;
  }
}

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

const freqMap = { a: 1, b: 2, c: 3 };
const root = buildTree(freqMap);
console.log(root.left.char);

A ReferenceError

B TypeError

C null

D undefined

💡 Hint

Check what happens when accessing char of merged nodes.

The merged node has char set to null, so root.left.char is the char of the left child node, which is defined. The output is the character of the left node, which is a string like 'a' or 'b'. But since root.left is a Node with char property, it prints the character. However, if the left node is a merged node with char null, it prints null. In this example, root.left.char is 'a' or 'b' depending on sorting. But the code prints root.left.char which is defined, so output is a character string, not undefined. But since the code prints root.left.char, and left is a Node with char property, the output is a character string, so option D 'undefined' is incorrect. The correct output is 'a'. Since 'a' is not an option, the closest is 'undefined' which is incorrect. So the code runs without error and prints a character. So options B, C, D are errors, but code runs fine. So none of the options match output. This means the question is invalid. To fix, change options to include the actual output 'a'.

❓ Predict Output

advanced

Output of Huffman Encoding Map Generation

What is the output of the following code that generates Huffman codes for characters?

DSA Javascript

class Node {
  constructor(char, freq, left = null, right = null) {
    this.char = char;
    this.freq = freq;
    this.left = left;
    this.right = right;
  }
}

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

function generateCodes(node, prefix = '', codes = {}) {
  if (!node.left && !node.right) {
    codes[node.char] = prefix;
  } else {
    if (node.left) generateCodes(node.left, prefix + '0', codes);
    if (node.right) generateCodes(node.right, prefix + '1', codes);
  }
  return codes;
}

const freqMap = { a: 2, b: 3, c: 5 };
const root = buildTree(freqMap);
const codes = generateCodes(root);
console.log(JSON.stringify(codes));

A {"a":"0","b":"10","c":"11"}

B {"a":"1","b":"0","c":"00"}

C {"a":"0","b":"11","c":"10"}

D {"a":"00","b":"01","c":"1"}

💡 Hint

The smallest frequencies get the longest codes, and the largest frequency gets the shortest code.

Frequencies: a=2, b=3, c=5. The tree merges a and b first (2+3=5), then merges with c (5). Codes assigned: a=0, b=10, c=11.

🧠 Conceptual

expert

Minimum Weighted Path Length in Huffman Tree

Given characters with frequencies {x: 1, y: 1, z: 2, w: 4}, what is the minimum weighted path length (sum of frequency * code length) of the Huffman encoding?

A 9

B 10

C 8

D 7

💡 Hint

Build the Huffman tree and calculate sum of frequency times code length for each character.

Constructing the tree and assigning codes results in weighted path length 9.

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