Huffman Encoding in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a frequency map from the input string.

DSA Typescript

const frequencyMap: Record<string, number> = {};
for (const char of input) {
  frequencyMap[char] = (frequencyMap[char] || 0) [1] 1;
}

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition.

Using multiplication or division which doesn't make sense here.

We add 1 to the current count for each character to build the frequency map.

2fill in blank

medium

Complete the code to sort the nodes by frequency in ascending order.

DSA Typescript

nodes.sort((a, b) => a.frequency [1] b.frequency);

Drag options to blanks, or click blank then click option'

A*

B+

C-

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition which does not sort correctly.

Using multiplication or division which are invalid here.

Subtracting frequencies sorts the array in ascending order.

3fill in blank

hard

Fix the error in the code that merges two nodes into a new parent node.

DSA Typescript

const mergedNode = {
  character: null,
  frequency: left.frequency [1] right.frequency,
  left: left,
  right: right
};

Drag options to blanks, or click blank then click option'

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction which can cause negative frequencies.

Using multiplication or division which are incorrect here.

The frequency of the merged node is the sum of the two child nodes' frequencies.

4fill in blank

hard

Fill both blanks to assign codes recursively to the Huffman tree nodes.

DSA Typescript

function assignCodes(node: Node | null, code: string) {
  if (!node) return;
  if (node.character !== null) {
    codes[node.character] = code;
  }
  assignCodes(node.[1], code + '0');
  assignCodes(node.[2], code + '1');
}

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cparent

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using parent or root which are not children nodes.

Swapping left and right which reverses codes.

We traverse left child with '0' and right child with '1' to assign codes.

5fill in blank

hard

Fill all three blanks to build the Huffman tree by merging nodes until one remains.

DSA Typescript

while (nodes.length > 1) {
  const left = nodes.shift();
  const right = nodes.shift();
  const mergedNode = {
    character: null,
    frequency: left.frequency [1] right.frequency,
    left: left,
    right: right
  };
  nodes.push(mergedNode);
  nodes.sort((a, b) => a.frequency [2] b.frequency);
}
const root = nodes.[3]();

Drag options to blanks, or click blank then click option'

A+

B-

Cpop

Dshift

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition for frequency sum.

Using addition instead of subtraction in sort comparator.

Using shift instead of pop to get the root node.

We sum frequencies to merge nodes, sort ascending by subtracting frequencies, and finally pop the root node.