Log inSign up
hardGeeksforGeeksNot Started

Huffman Coding

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a string S of N distinct characters and their frequencies f[], construct a Huffman Tree and return the Huffman codes for all characters in preorder traversal order of the tree.

Huffman coding is a lossless data compression algorithm where frequently occurring characters receive shorter binary codes, and less frequent characters receive longer codes.

Example 1 · Example 1: Six Characters:

Input: S = "abcdef", f = [5, 9, 12, 13, 16, 45]
Output: ["0", "100", "101", "1100", "1101", "111"]
Explanation: Character f (freq 45) gets the shortest code 0, while a (freq 5) and b (freq 9) merge early and receive longer prefix codes.

Constraints:

  • 1 <= N <= 104
  • S consists of distinct lowercase English letters.
  • 1 <= f[i] <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the greedy choice property in optimal merge patterns.
  • Construct a binary prefix tree and generate variable-length prefix codes.
  • Implement the min-heap based Huffman encoding across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Optimal lossless compression or variable-length encoding.
  • Repeatedly combine two smallest elements into one.
  • Weighted path length minimization.

Algorithmic Decision Tree:

  • If characters are already sorted by frequency -> Two Queues can achieve O(N) time.
  • If unsorted -> Min-Heap achieves O(N log N) time.

Connected Patterns:

Minimum Cost to Connect Sticks / Connect RopesMerge K Sorted Lists

1. Linear Scan Merge

Intuition

Maintain a dynamic list of active trees. Repeatedly scan linearly across all elements to find and remove the two minimum frequency nodes, merge them, and append the parent.

Algorithm

  1. Step 1: Create leaf nodes for each character and place them in an array.
  2. Step 2: Loop N-1 times: scan the array to locate the indices of the two nodes with minimal frequencies.
  3. Step 3: Remove those two nodes, create a parent node with left and right children and summed frequency.
  4. Step 4: Add the parent back to the array.
  5. Step 5: Perform preorder traversal on the final remaining root node to generate binary codes.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8struct Node {
9 char data;
10 int freq;
11 Node *left, *right;
12 Node(char d, int f) : data(d), freq(f), left(nullptr), right(nullptr) {}
13};
14
15class Solution {
16 void preorder(Node* root, string code, vector<string>& ans) {
17 if (!root) return;
18 if (!root->left && !root->right) {
19 ans.push_back(code.empty() ? "0" : code);
20 return;
21 }
22 preorder(root->left, code + "0", ans);
23 preorder(root->right, code + "1", ans);
24 }
25public:
26 vector<string> huffmanCodes(string S, vector<int>& f, int N) {
27 vector<Node*> nodes;
28 for (int i = 0; i < N; ++i) nodes.push_back(new Node(S[i], f[i]));
29
30 while (nodes.size() > 1) {
31 int min1 = 0;
32 for (int i = 1; i < (int)nodes.size(); ++i) {
33 if (nodes[i]->freq < nodes[min1]->freq) min1 = i;
34 }
35 Node* leftNode = nodes[min1];
36 nodes.erase(nodes.begin() + min1);
37
38 int min2 = 0;
39 for (int i = 1; i < (int)nodes.size(); ++i) {
40 if (nodes[i]->freq < nodes[min2]->freq) min2 = i;
41 }
42 Node* rightNode = nodes[min2];
43 nodes.erase(nodes.begin() + min2);
44
45 Node* parent = new Node(', leftNode->freq + rightNode->freq);, leftNode->freq + rightNode->freq);
46 parent->left = leftNode;
47 parent->right = rightNode;
48 nodes.push_back(parent);
49 }
50
51 vector<string> ans;
52 if (!nodes.empty()) preorder(nodes[0], "", ans);
53 return ans;
54 }
55};
56
57int main() {
58 Solution sol;
59 string S = "abcdef";
60 vector<int> f = {5, 9, 12, 13, 16, 45};
61 vector<string> codes = sol.huffmanCodes(S, f, S.size());
62 cout << "Huffman Codes (Preorder):" << endl;
63 for (const string& code : codes) {
64 cout << code << " ";
65 }
66 cout << endl;
67 return 0;
68}

Time & Space Complexity

  • Time complexity: O(N^2)
  • Space complexity: O(N)

2. Two Queues Linear Merge

Intuition

Sort leaves initially by frequency into Queue 1. Put merged nodes into Queue 2. The minimum element is always the minimum of the two queue fronts.

Algorithm

  1. Step 1: Sort characters by frequency ascending and insert all leaf nodes into Queue 1.
  2. Step 2: Maintain an empty Queue 2 for combined parent nodes.
  3. Step 3: At each step, extract the node with minimum frequency by comparing the fronts of Queue 1 and Queue 2.
  4. Step 4: Repeat extraction to get the second minimum node.
  5. Step 5: Create a new parent node, set children, and push it into the back of Queue 2.
  6. Step 6: Repeat until both queues have only 1 total node combined. Traverse preorder.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <queue>
5#include <algorithm>
6
7using namespace std;
8
9struct Node {
10 char data;
11 int freq;
12 Node *left, *right;
13 Node(char d, int f) : data(d), freq(f), left(nullptr), right(nullptr) {}
14};
15
16class Solution {
17 Node* getMinNode(queue<Node*>& q1, queue<Node*>& q2) {
18 if (q1.empty()) {
19 Node* front = q2.front(); q2.pop(); return front;
20 }
21 if (q2.empty()) {
22 Node* front = q1.front(); q1.pop(); return front;
23 }
24 if (q1.front()->freq <= q2.front()->freq) {
25 Node* front = q1.front(); q1.pop(); return front;
26 } else {
27 Node* front = q2.front(); q2.pop(); return front;
28 }
29 }
30
31 void preorder(Node* root, string code, vector<string>& ans) {
32 if (!root) return;
33 if (!root->left && !root->right) {
34 ans.push_back(code.empty() ? "0" : code);
35 return;
36 }
37 preorder(root->left, code + "0", ans);
38 preorder(root->right, code + "1", ans);
39 }
40public:
41 vector<string> huffmanCodes(string S, vector<int>& f, int N) {
42 vector<pair<int, char>> items(N);
43 for (int i = 0; i < N; ++i) items[i] = {f[i], S[i]};
44 sort(items.begin(), items.end());
45
46 queue<Node*> q1, q2;
47 for (int i = 0; i < N; ++i) {
48 q1.push(new Node(items[i].second, items[i].first));
49 }
50
51 while (!(q1.empty() && q2.size() == 1)) {
52 Node* left = getMinNode(q1, q2);
53 Node* right = getMinNode(q1, q2);
54
55 Node* parent = new Node(', left->freq + right->freq);, left->freq + right->freq);
56 parent->left = left;
57 parent->right = right;
58 q2.push(parent);
59 }
60
61 vector<string> ans;
62 Node* root = q2.front();
63 preorder(root, "", ans);
64 return ans;
65 }
66};
67
68int main() {
69 Solution sol;
70 string S = "abcdef";
71 vector<int> f = {5, 9, 12, 13, 16, 45};
72 vector<string> codes = sol.huffmanCodes(S, f, S.size());
73 cout << "Huffman Codes (Two Queues):" << endl;
74 for (const string& code : codes) cout << code << " ";
75 cout << endl;
76 return 0;
77}

Time & Space Complexity

  • Time complexity: O(N log N)
  • Space complexity: O(N)

3. Min-Heap / Priority Queue

Intuition

Push all character nodes into a min-priority queue. Repeatedly extract the two minimum nodes, merge into a parent node, and push back until 1 root remains. Traverse preorder.

Algorithm

  1. Step 1: Create a Min-Heap and push all characters as leaf nodes with their frequencies.
  2. Step 2: While heap size > 1, extract min node as left child and second min node as right child.
  3. Step 3: Create an internal node with freq = left.freq + right.freq, set children, and push back into heap.
  4. Step 4: The last remaining element is the root of the Huffman Tree.
  5. Step 5: Perform preorder traversal (left edge 0, right edge 1) and record codes for all leaf nodes.

Interactive Trace for Huffman Tree Construction

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Extract two minimum nodes: 'a' (5) and 'b' (9)
Visual state
Values and pointers at this exact step
pointers
S
merged
merged
pending
pending
0
↑ merged
1
2
3
Check / comparison
Min1 = 'a' (5), Min2 = 'b' (9) -> Parent weight = 14
Decision / next transition
Push P1(14) into min-heap.
Why this step matters

Step 1: Extract two minimum nodes: a (5) and b (9). Merge into node P1 with frequency 14.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <queue>
5
6using namespace std;
7
8struct Node {
9 char data;
10 int freq;
11 Node *left, *right;
12 Node(char d, int f) : data(d), freq(f), left(nullptr), right(nullptr) {}
13};
14
15struct Compare {
16 bool operator()(Node* a, Node* b) {
17 return a->freq > b->freq;
18 }
19};
20
21class Solution {
22 void preorder(Node* root, string code, vector<string>& ans) {
23 if (!root) return;
24 if (!root->left && !root->right) {
25 ans.push_back(code.empty() ? "0" : code);
26 return;
27 }
28 preorder(root->left, code + "0", ans);
29 preorder(root->right, code + "1", ans);
30 }
31public:
32 vector<string> huffmanCodes(string S, vector<int>& f, int N) {
33 priority_queue<Node*, vector<Node*>, Compare> minHeap;
34 for (int i = 0; i < N; ++i) {
35 minHeap.push(new Node(S[i], f[i]));
36 }
37
38 while (minHeap.size() > 1) {
39 Node* left = minHeap.top(); minHeap.pop();
40 Node* right = minHeap.top(); minHeap.pop();
41
42 Node* parent = new Node(', left->freq + right->freq);, left->freq + right->freq);
43 parent->left = left;
44 parent->right = right;
45 minHeap.push(parent);
46 }
47
48 vector<string> ans;
49 if (!minHeap.empty()) preorder(minHeap.top(), "", ans);
50 return ans;
51 }
52};
53
54int main() {
55 Solution sol;
56 string S = "abcdef";
57 vector<int> f = {5, 9, 12, 13, 16, 45};
58 vector<string> codes = sol.huffmanCodes(S, f, S.size());
59 cout << "Huffman Codes (Min-Heap):" << endl;
60 for (const string& code : codes) cout << code << " ";
61 cout << endl;
62 return 0;
63}

Time & Space Complexity

  • Time complexity: O(N log N)
  • Space complexity: O(N)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Linear Scan for MinimumsO(N^2)O(N)Maintain an active list of tree nodes. In each of the N-1 steps, scan the list linearly to find the two nodes with the smallest frequencies, remove them, and append their merged parent.Repeated linear scan to find minimums.
2.Better — Two Queues (when sorted)O(N log N) or O(N) if presortedO(N)Sort initial character nodes into Queue 1. Push merged parent nodes into Queue 2. The minimum element is always at the front of either Queue 1 or Queue 2.Initial sorting if unsorted.
3.Optimal — Priority Queue / Min-HeapOptimalO(N log N)O(N)Insert all leaf nodes into a min-priority queue. Pop two minimum nodes, merge them with a new parent, and push the parent back into the min-heap until only 1 root node remains. Traverse preorder to collect prefix codes.N log N heap operations.
Back to DSA Sheet