Huffman Encoding in DSA Javascript - Time & Space Complexity

Time Complexity: Huffman Encoding

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to build a Huffman tree changes as the number of characters grows.

How does the work increase when we have more characters to encode?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function buildHuffmanTree(freqMap) {
  const heap = new MinHeap();
  for (const char in freqMap) {
    heap.insert({char, freq: freqMap[char]});
  }
  while (heap.size() > 1) {
    const left = heap.extractMin();
    const right = heap.extractMin();
    const merged = {freq: left.freq + right.freq, left, right};
    heap.insert(merged);
  }
  return heap.extractMin();
}
    

This code builds a Huffman tree by repeatedly combining the two smallest frequency nodes until one tree remains.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that extracts two minimum nodes and inserts their merged node back into the heap.
• How many times: This loop runs about n-1 times, where n is the number of unique characters.

How Execution Grows With Input

Each loop step involves removing two nodes and adding one back, with heap operations taking time based on heap size.

Input Size (n)	Approx. Operations
10	About 10 log 10 operations
100	About 100 log 100 operations
1000	About 1000 log 1000 operations

Pattern observation: The work grows a bit faster than just the number of characters because of the log factor from heap operations.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to build the Huffman tree grows a little more than linearly as the number of characters increases.

Common Mistake

[X] Wrong: "Building the Huffman tree takes only linear time because we just combine nodes."

[OK] Correct: Each combination involves heap operations that take logarithmic time, so the total time is more than just linear.

Interview Connect

Understanding how Huffman encoding scales helps you explain efficient data compression and priority queue use in real problems.

Self-Check

"What if we used a simple sorted array instead of a heap for selecting minimum nodes? How would the time complexity change?"

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