Tree Applications

Huffman Coding

What is Huffman Coding?

Huffman coding compresses data by giving frequent symbols short binary codes and rare symbols longer ones — the opposite of fixed-width encodings like ASCII, where every character costs the same 8 bits regardless of how often it appears. The codes it produces are prefix-free: no character's code is a prefix of another's, which means a stream of bits can be decoded unambiguously without any separators between codes.

How Does It Work?

The codes come directly out of a binary tree built specifically for this purpose. Every leaf holds one symbol, and a symbol's code is the sequence of left/right turns (0s and 1s) on the path from the root down to its leaf. Because frequent symbols end up near the root and rare ones get pushed deeper, frequent symbols naturally get shorter codes.

That tree is built greedily, bottom-up: start with every symbol as its own single-node tree, weighted by its frequency. Repeatedly take the two trees with the smallest total weight and merge them under a new parent node (weight = the sum of the two), putting the result back into the pool. After enough merges only one tree remains — the Huffman tree — and it's provably optimal: no other prefix-free code achieves a shorter total encoded length for that exact frequency distribution.

a is frequent and gets the short code 0; b and c are rarer and get longer codes 10, 11
0101•a•bc

Algorithm Steps

  1. Count how often each symbol appears in the input
  2. Put every symbol into a priority queue as a single-node tree, ordered by frequency
  3. Repeat until one tree remains:
    • Remove the two trees with the smallest frequency
    • Merge them under a new internal node whose frequency is their sum
    • Insert the merged tree back into the queue
  4. Assign each symbol's code by reading the path from the root to its leaf — 0 for left, 1 for right

Time Complexity

  • Time Complexity: O(n log n), where n is the number of distinct symbols — each of the n-1 merges costs O(log n) with a priority queue.
  • Space Complexity: O(n) for the tree and the code table.

Time Complexity Analysis

Advertisement

Huffman coding is a building block inside many real compression formats — it's the final entropy-coding stage in DEFLATE (used by ZIP and gzip), JPEG, and MP3, typically applied after some other transform has already reduced redundancy in the data.

Daily DSA Challenge by Scale Engineer

Build an optimal prefix-free binary code by repeatedly merging the two rarest symbols

Enter text and build its Huffman tree

Huffman Tree

Build a tree to see it appear here
Internal nodeLeaf (character)RootEdge bit (0 = left, 1 = right)

Test Your Knowledge before moving forward!

Huffman Coding Quiz

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Huffman Coding Implementation

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

// Repeatedly merges the two lowest-frequency nodes until one tree remains.
function buildHuffmanTree(text) {
  const freqMap = {};
  for (const ch of text) freqMap[ch] = (freqMap[ch] || 0) + 1;

  let nodes = Object.entries(freqMap).map(([char, freq]) => new HuffmanNode(char, freq));

  while (nodes.length > 1) {
    nodes.sort((a, b) => a.freq - b.freq);
    const [a, b] = nodes;
    const merged = new HuffmanNode(null, a.freq + b.freq, a, b);
    nodes = nodes.slice(2).concat([merged]);
  }

  return nodes[0]; // root
}

// Root-to-leaf path gives each character's code: 0 for left, 1 for right.
function buildCodes(node, path = "", codes = {}) {
  if (!node) return codes;
  if (node.left === null && node.right === null) {
    codes[node.char] = path || "0";
    return codes;
  }
  buildCodes(node.left, path + "0", codes);
  buildCodes(node.right, path + "1", codes);
  return codes;
}

function encode(text) {
  const root = buildHuffmanTree(text);
  const codes = buildCodes(root);
  const encoded = [...text].map((ch) => codes[ch]).join("");
  return { encoded, codes };
}

// Usage example
encode("abracadabra");
// codes: { a: "0", b: "111", r: "10", c: "1100", d: "1101" } (exact codes vary by tie-breaking)

Done With the Learning

Mark Huffman Coding as done and view it on your dashboard

Explore Other Tree Topics

Heap Sort

Decision Trees

Syntax Trees

Tree Diameter

Lowest Common Ancestor

Level-order Traversal

Structure & Properties