Working with Graphs & Trees

What type of tree is being constructed for data compression?

function buildHuffmanTree(frequencies) {
  const pq = new PriorityQueue();
  
  for (let [char, freq] of Object.entries(frequencies)) {
    pq.enqueue({ char, freq }, freq);
  }
  
  while (pq.size() > 1) {
    const left = pq.dequeue();
    const right = pq.dequeue();
    const parent = {
      freq: left.freq + right.freq,
      left,
      right
    };
    pq.enqueue(parent, parent.freq);
  }
  
  return pq.dequeue();
}

Binary Search Tree
Prefix Tree
Huffman Tree
This constructs a Huffman Tree because: 1) Uses character frequencies to build optimal prefix codes, 2) Combines lowest frequency nodes first, 3) Creates variable-length encoding based on frequency, 4) Uses priority queue for efficient construction, 5) Results in minimum-weighted path lengths, 6) Common in data compression algorithms, 7) O(n log n) construction time where n is number of characters, 8) Optimal for variable-length prefix coding.
Expression Tree

Next Question (21/21)