Loading…

mediumTreesSometimes asked

Tree: Huffman Decoding

Q: How do you solve Tree: Huffman Decoding using the Tree Walk — One Bit at a Time, Reset at Leaves (Optimal) approach?

When to use it: The canonical answer. Lead with it — it's O(L) time, O(1) space, and uses the tree directly. Decoding is a guided descent where the *input string*, not the tree's own structure, decides the path. **Bits are directions.** Start with a pointer at the root. Read the bits left to right: on `'0'` move to the left child, on `'1'` move to the right child. Each bit advances the pointer one edge deeper. **Leaves are emit points.** Internal nodes are just junctions; only leaves hold real characters. The moment the pointer lands on a leaf (both children null), one full codeword has been traced from root to leaf — so append that leaf's character to the output and **reset the pointer to the root** to begin the next character. **Why no ambiguity or backtracking.** Huffman codes are *prefix-free*: no character's codeword is a prefix of another's. Structurally, that means every character sits at a leaf and no character sits at an internal node along the way to another. Therefore the first leaf you reach is unambiguously the end of exactly one character — you never need to look ahead or undo a step. This is the property that makes the simple 'stop at the first leaf' rule correct. **Why reset matters.** Forgetting to reset to the root after an emit is the classic bug: the pointer would keep descending from the leaf (which has no children), either crashing on a null move or silently producing garbage. Resetting restarts the next codeword from the top of the tree. Time complexity: O(L). Space complexity: O(1).

Q: How do you solve Tree: Huffman Decoding using the Prefix-Table Decode — Build code→char Map First approach?

When to use it: Offer as an alternative or when you'll decode many strings against the same tree and want a reusable lookup. Instead of walking the tree per bit, precompute the dictionary once and then match prefixes in the string. **Build the codebook.** DFS the tree carrying the path string built so far: append `'0'` going left, `'1'` going right. At each leaf, record `code → character` in a map. This single traversal captures every codeword. **Decode by prefix matching.** Walk the encoded string accumulating bits into a buffer. After each bit, check whether the buffer matches a key in the map. The prefix-free property guarantees that as soon as the buffer equals some code, it can't be the prefix of a different code, so the match is unambiguous — emit that character, clear the buffer, and keep scanning. **Trade-offs versus the tree walk.** This uses O(N) extra space for the map and O(N) preprocessing, so for a single decode the direct tree walk is strictly simpler and lighter. The table shines when you decode *many* strings against the *same* tree: you build the map once and reuse it, and the per-string cost is O(L). It also generalizes to non-binary tries. Functionally the two produce identical output because both rely on the same prefix-free structure. Time complexity: O(L + N). Space complexity: O(N).

Trees & BST · 36 of 41 · 9 min

You are given the root of a prebuilt Huffman tree and an encoded binary string s. In the tree, every leaf stores one original character; internal nodes are structural placeholders. The encoding assigns each character the sequence of left/right turns ('0' = left, '1' = right) from the root to its leaf.

Decode s back into the original string and print it.

In plain English

Treat the bit string as step-by-step directions through the tree. Each bit moves you one edge down; whenever you arrive at a leaf you've completed one character's codeword, so you output that character and jump back to the root to start decoding the next one. The prefix-free property of Huffman codes is what makes 'stop at the first leaf' always correct.

Examples

Example 1

Input: Tree: A='1', B='00', C='01'; s = "1001011"
Output: ABACA
Note: 1→A, 00→B, 1→A, 01→C, 1→A. Reset to root after each leaf.

Example 2

Input: Tree: A='1', B='00', C='01'; s = "1"
Output: A
Note: A single right turn lands on leaf A.

Example 3

Input: Tree: A='1', B='00', C='01'; s = "0001"
Output: BC
Note: 00 → B (reset), 01 → C. The two codewords are read back to back.

Constraints

1 ≤ |s| ≤ 25 (encoded length, per typical test bounds)
The Huffman tree is already built and valid (prefix-free)
Every leaf holds exactly one character; internal nodes hold a placeholder
'0' means go left, '1' means go right

Clarifying questions4First question: Is the tree already built, or do I build it from frequencies?Explore questions

Q1.Is the tree already built, or do I build it from frequencies?
Already built. This is the decode side. Building the tree from character frequencies with a min-heap is the separate encoding problem.
Q2.How do I know a node is a leaf?
Both children are null. Only leaves carry real characters; internal nodes have a placeholder value you must not emit.
Q3.Which direction is 0 and which is 1?
By convention '0' goes left and '1' goes right. The tree was encoded with that convention, so decoding must match it.
Q4.Why don't I need to look ahead or backtrack?
Huffman codes are prefix-free: no codeword is a prefix of another. So the first leaf you hit is unambiguously the end of exactly one character — no lookahead required.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Decode by walking the prebuilt Huffman tree one bit at a time: start at the root, go LEFT on '0' and RIGHT on '1'. Because Huffman codes are prefix-free, every codeword ends exactly at a leaf — so the moment you land on a leaf, append its character and reset back to the root. Repeat until the bit string is consumed. It's O(L) time in the length of the encoded string and O(1) extra space; the tree does all the disambiguation for you.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can drive a tree traversal from an external bit string, detect leaves correctly, and exploit the prefix-free property to decode unambiguously in one pass.

Where candidates slip

Forgetting to reset to the root after emitting a character, mis-detecting leaves (emitting at internal nodes), or swapping the 0=left / 1=right convention.

How to stand out

Explain WHY no backtracking is needed (prefix-free codes end at leaves), keep the walk to O(1) space, and contrast with the encoding side (building the tree from a min-heap).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Tree Walk — One Bit at a Time, Reset at Leaves (Optimal)Optimal	`O(L)`	`O(1)`	The canonical answer. Lead with it — it's O(L) time, O(1) space, and uses the tree directly.	Read
2	Prefix-Table Decode — Build code→char Map First	`O(L + N)`	`O(N)`	Offer as an alternative or when you'll decode many strings against the same tree and want a reusable lookup.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewat node, read bitbit == '0'?YesNoExplore the full tree

Decode loop

How to read it:Each bit is a turn; a leaf triggers an emit and a reset to the root.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Tree Walk — One Bit at a Time, Reset at Leaves (Optimal)

TimeO(L)SpaceO(1)

The canonical answer. Lead with it — it's O(L) time, O(1) space, and uses the tree directly.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Think of each bit as a single instruction: which child do you move to on '0' vs '1'?

2Hint 2Explore hint

Keep a pointer at the root and move it down one edge per bit. When does a codeword end?

3Hint 3Explore hint

A codeword ends at a leaf (both children null). Emit the leaf's character, reset the pointer to the root, and continue with the next bit.

A · Core idea

Decoding is a guided descent where the input string, not the tree's own structure, decides the path.

Bits are directions. Start with a pointer at the root. Read the bits left to right: on '0' move to the left child, on '1' move to the right child. Each bit advances the pointer one edge deeper.

Leaves are emit points. Internal nodes are just junctions; only leaves hold real characters. The moment the pointer lands on a leaf (both children null), one full codeword has been traced from root to leaf — so append that leaf's character to the output and reset the pointer to the root to begin the next character.

Why no ambiguity or backtracking. Huffman codes are prefix-free: no character's codeword is a prefix of another's. Structurally, that means every character sits at a leaf and no character sits at an internal node along the way to another. Therefore the first leaf you reach is unambiguously the end of exactly one character — you never need to look ahead or undo a step. This is the property that makes the simple 'stop at the first leaf' rule correct.

Why reset matters. Forgetting to reset to the root after an emit is the classic bug: the pointer would keep descending from the leaf (which has no children), either crashing on a null move or silently producing garbage. Resetting restarts the next codeword from the top of the tree.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

Tree A='1', B='00', C='01'; s = "1001011"

Huffman tree for A,B,C

How to read it:A='1' (right). B='00', C='01' (left then left/right).

Rendering diagram…

Final resultABACA

C · Code with teaching comments

solution.javaJava

Tree Walk — One Bit at a Time, Reset at Leaves (Optimal) — optimal

4 teaching notes

1
// Definition for a Huffman tree node.
2
class Node {
3
    int freq;
4
    char data;        // meaningful only at leaves
5
    Node left;
6
    Node right;
7
}
8
 
9
void decode(String s, Node root) {
10
    StringBuilder out = new StringBuilder();
11
    Node node = root;
12
    for (int i = 0; i < s.length(); i++) {
13
        node = (s.charAt(i) == '0') ? node.left : node.right;  // 0=left, 1=right
14
        if (node.left == null && node.right == null) {          // leaf reached
15
            // Emit the leaf's character — only leaves carry real data.
16
            out.append(node.data);
17
            node = root;                                        // reset for next code
18
        }
19
    }
20
    System.out.println(out.toString());
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(L) timeO(1) spaceOpen the invariant and proofExplore the proof

The encoded string is a tape of turn-left / turn-right instructions, and the prefix-free tree guarantees each character's instructions end precisely at a leaf. Decoding is therefore a single linear pass with a reset — no heap, no lookahead, O(1) space.

ComplexityO(L) time, O(1) space — Each of the L bits causes exactly one pointer move and O(1) leaf check → O(L) time. Only a single node pointer and the output buffer are used → O(1) auxiliary space (excluding the output itself).

E · Edge cases and pitfalls6s with a single 1-bit codeword — One turn to a leaf → emit one character.Explore edge cases

Edge cases handled

s with a single 1-bit codewordOne turn to a leaf → emit one character.
Two codewords back to back (e.g. 0001)Reset after the first leaf lets the second codeword start cleanly.
Tree with a single leaf (one distinct char)Each bit lands on the lone leaf; emit and reset every bit.

Pitfalls

Not resetting to the root after an emit — descends off a leaf and crashes or garbles output.
Emitting at internal nodes — their data is a placeholder, not a character.
Swapping the 0=left / 1=right convention — decodes to the wrong characters.

03.2

Approach 2 of 2

Prefix-Table Decode — Build code→char Map First

TimeO(L + N)SpaceO(N)

Offer as an alternative or when you'll decode many strings against the same tree and want a reusable lookup.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Traverse the tree once, accumulating the path ('0'/'1') to each leaf, to build a code→character dictionary.

2Hint 2Explore hint

Then scan the encoded string, accumulating bits until the running prefix matches a code in the dictionary.

3Hint 3Explore hint

Because codes are prefix-free, the first match is unambiguous — emit, clear the buffer, and continue.

A · Core idea

Instead of walking the tree per bit, precompute the dictionary once and then match prefixes in the string.

Build the codebook. DFS the tree carrying the path string built so far: append '0' going left, '1' going right. At each leaf, record code → character in a map. This single traversal captures every codeword.

Decode by prefix matching. Walk the encoded string accumulating bits into a buffer. After each bit, check whether the buffer matches a key in the map. The prefix-free property guarantees that as soon as the buffer equals some code, it can't be the prefix of a different code, so the match is unambiguous — emit that character, clear the buffer, and keep scanning.

Trade-offs versus the tree walk. This uses O(N) extra space for the map and O(N) preprocessing, so for a single decode the direct tree walk is strictly simpler and lighter. The table shines when you decode many strings against the same tree: you build the map once and reuse it, and the per-string cost is O(L). It also generalizes to non-binary tries. Functionally the two produce identical output because both rely on the same prefix-free structure.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

Tree A='1', B='00', C='01'; s = "0001"

Codebook from the tree

How to read it:DFS paths to leaves: A='1', B='00', C='01'.

Rendering diagram…

Final resultBC

C · Code with teaching comments

Reference implementation previewimport java.util.*; Map<String, Character> buildCodes(Node node, String path, Map<String, Character> map) { if (node == null) return map; if (node.left == null && node.right == null) { // leafExplore the full code

solution.javaJava

Prefix-Table Decode — Build code→char Map First — reference

4 teaching notes

1
import java.util.*;
2
 
3
Map<String, Character> buildCodes(Node node, String path, Map<String, Character> map) {
4
    if (node == null) return map;
5
    if (node.left == null && node.right == null) {   // leaf
6
        map.put(path.isEmpty() ? "0" : path, node.data);
7
        return map;
8
    }
9
    // Left edge contributes a '0' to the codeword.
10
    buildCodes(node.left, path + "0", map);
11
    buildCodes(node.right, path + "1", map);
12
    return map;
13
}
14
 
15
void decode(String s, Node root) {
16
    Map<String, Character> codes = buildCodes(root, "", new HashMap<>());
17
    StringBuilder out = new StringBuilder();
18
    StringBuilder buf = new StringBuilder();
19
    for (int i = 0; i < s.length(); i++) {
20
        buf.append(s.charAt(i));
21
        // Check if the current bit buffer exactly matches a codeword.
22
        Character c = codes.get(buf.toString());
23
        if (c != null) {                              // prefix-free → first match is final
24
            out.append(c);
25
            buf.setLength(0);
26
        }
27
    }
28
    System.out.println(out.toString());
29
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.29 lines

D · Why it works and complexityO(L + N) timeO(N) spaceOpen the invariant and proofExplore the proof

The tree walk and the prefix table are the same algorithm wearing different clothes: both exploit prefix-freeness so the first complete codeword is unambiguous. Pick the table only when amortizing the build across many decodes; otherwise the O(1)-space tree walk wins.

ComplexityO(L + N) time, O(N) space — Building the table visits all N tree nodes → O(N). Decoding scans L bits, each appended and checked in O(1) average against the map → O(L). Total O(L + N); the map costs O(N) space.

E · Edge cases and pitfalls6Single-leaf tree — Path is empty; guard it to a placeholder code like '0' so the lookup works.Explore edge cases

Edge cases handled

Single-leaf treePath is empty; guard it to a placeholder code like '0' so the lookup works.
Many strings, same treeBuild the map once, reuse it — this is when the table beats the walk.
Empty encoded stringNo bits → empty output.

Pitfalls

Building the map for every decode call when the tree is reused — wastes the table's advantage.
Not clearing the buffer after a match — concatenates codes and never matches again.
Mishandling the single-leaf empty-path case.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a Huffman tree node. class Node { int freq; char data; // meaningful only at leaves Node left;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

No reset after emitting

After hitting a leaf you must restart at the root. Without the reset the pointer tries to descend from a childless leaf — a null move (crash) or garbage on subsequent bits.

Explore the code comparison

Don't write this

for bit in s:
    node = node.left if bit == '0' else node.right
    if node.left is None and node.right is None:
        out.append(node.data)
        # missing: node = root  -> next bit derefs a leaf's null child

Write this instead

for bit in s:
    node = node.left if bit == '0' else node.right
    if node.left is None and node.right is None:
        out.append(node.data)
        node = root   # restart the next codeword from the top

Emitting at internal nodes

Internal nodes are structural and their data field is a placeholder. Emitting there produces placeholder characters in the output; only leaves hold real data.

Explore the code comparison

Don't write this

node = (bit == '0') ? node.left : node.right;
out.append(node.data);   // wrong: appends even at internal nodes

Write this instead

node = (bit == '0') ? node.left : node.right;
if (node.left == null && node.right == null) {  // only at leaves
    out.append(node.data);
    node = root;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Walk the Huffman tree per bit; emit at each leaf, reset to root

Code pattern to memorize

node = root
for bit in s:
    node = node.left if bit == '0' else node.right
    if node is a leaf:
        emit(node.data)
        node = root

Rules to remember

1'0' goes left, '1' goes right — the convention the tree was built with.
2A node is a leaf when both children are null; only leaves carry real characters.
3On reaching a leaf, emit its character and reset to the root for the next codeword.
4Huffman codes are prefix-free, so a leaf is reached at exactly one unambiguous point — no backtracking.
5Don't try to emit at internal nodes; their data is a placeholder, not an output character.

Use this pattern when

Decoding a bit stream against a known prefix-code (Huffman) tree
Any decode where the dictionary is structured as a trie/binary tree
Walking a tree driven by an external sequence of left/right instructions

Choose another pattern when

You must BUILD the Huffman tree from frequencies → that's the encoding/priority-queue problem, not this
Codes are fixed-length → index directly, no tree walk needed
Codes are not prefix-free → tree decoding is ambiguous; a different scheme is required

Interview takeaway

Huffman decoding is a guided tree walk: the bits are turnstile instructions, leaves are output points, and the prefix-free property guarantees you always know exactly when a character ends. Reset to the root after every emit and the whole thing is one clean pass.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternDecode a prefix-free code by walking a binary tree under external instructions: bits choose left/right, leaves are emit points, and a reset-to-root after each leaf starts the next codeword. The prefix-free property guarantees unambiguous single-pass decoding in O(L) time and O(1) space; a precomputed code→char table is the reuse-friendly variant.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Build a Huffman Tree (Encoding)
Coming soon
Use a min-heap of frequencies; repeatedly merge the two lowest into a parent node.
Implement Trie (Prefix Tree)
Coming soon
Same idea generalized: walk a trie driven by characters instead of bits.
Tree: Preorder Traversal
Building the code table is a preorder DFS accumulating the path.
Tree: Level Order Traversal
Another externally-driven tree walk, by level instead of by bit.

Same pattern

←

Tree: Height of a Binary Tree

Continue · Next problem

Tree: Inorder Traversal

mediumTreesSometimes asked

Tree: Huffman Decoding

Trees & BST · 36 of 41 · 9 min

Decode s back into the original string and print it.

In plain English

Examples

Example 1

Input: Tree: A='1', B='00', C='01'; s = "1001011"
Output: ABACA
Note: 1→A, 00→B, 1→A, 01→C, 1→A. Reset to root after each leaf.

Example 2

Input: Tree: A='1', B='00', C='01'; s = "1"
Output: A
Note: A single right turn lands on leaf A.

Example 3

Input: Tree: A='1', B='00', C='01'; s = "0001"
Output: BC
Note: 00 → B (reset), 01 → C. The two codewords are read back to back.

Constraints

1 ≤ |s| ≤ 25 (encoded length, per typical test bounds)
The Huffman tree is already built and valid (prefix-free)
Every leaf holds exactly one character; internal nodes hold a placeholder
'0' means go left, '1' means go right

Clarifying questions4First question: Is the tree already built, or do I build it from frequencies?Explore questions

Q1.Is the tree already built, or do I build it from frequencies?
Already built. This is the decode side. Building the tree from character frequencies with a min-heap is the separate encoding problem.
Q2.How do I know a node is a leaf?
Both children are null. Only leaves carry real characters; internal nodes have a placeholder value you must not emit.
Q3.Which direction is 0 and which is 1?
By convention '0' goes left and '1' goes right. The tree was encoded with that convention, so decoding must match it.
Q4.Why don't I need to look ahead or backtrack?
Huffman codes are prefix-free: no codeword is a prefix of another. So the first leaf you hit is unambiguously the end of exactly one character — no lookahead required.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can drive a tree traversal from an external bit string, detect leaves correctly, and exploit the prefix-free property to decode unambiguously in one pass.

Where candidates slip

Forgetting to reset to the root after emitting a character, mis-detecting leaves (emitting at internal nodes), or swapping the 0=left / 1=right convention.

How to stand out

Explain WHY no backtracking is needed (prefix-free codes end at leaves), keep the walk to O(1) space, and contrast with the encoding side (building the tree from a min-heap).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Tree Walk — One Bit at a Time, Reset at Leaves (Optimal)Optimal	`O(L)`	`O(1)`	The canonical answer. Lead with it — it's O(L) time, O(1) space, and uses the tree directly.	Read
2	Prefix-Table Decode — Build code→char Map First	`O(L + N)`	`O(N)`	Offer as an alternative or when you'll decode many strings against the same tree and want a reusable lookup.	Read

Decode loop

How to read it:Each bit is a turn; a leaf triggers an emit and a reset to the root.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Tree Walk — One Bit at a Time, Reset at Leaves (Optimal)

TimeO(L)SpaceO(1)

The canonical answer. Lead with it — it's O(L) time, O(1) space, and uses the tree directly.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Think of each bit as a single instruction: which child do you move to on '0' vs '1'?

2Hint 2Explore hint

Keep a pointer at the root and move it down one edge per bit. When does a codeword end?

3Hint 3Explore hint

A codeword ends at a leaf (both children null). Emit the leaf's character, reset the pointer to the root, and continue with the next bit.

A · Core idea

Decoding is a guided descent where the input string, not the tree's own structure, decides the path.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

Tree A='1', B='00', C='01'; s = "1001011"

Huffman tree for A,B,C

How to read it:A='1' (right). B='00', C='01' (left then left/right).

Rendering diagram…

Final resultABACA

C · Code with teaching comments

solution.javaJava

Tree Walk — One Bit at a Time, Reset at Leaves (Optimal) — optimal

4 teaching notes

1
// Definition for a Huffman tree node.
2
class Node {
3
    int freq;
4
    char data;        // meaningful only at leaves
5
    Node left;
6
    Node right;
7
}
8
 
9
void decode(String s, Node root) {
10
    StringBuilder out = new StringBuilder();
11
    Node node = root;
12
    for (int i = 0; i < s.length(); i++) {
13
        node = (s.charAt(i) == '0') ? node.left : node.right;  // 0=left, 1=right
14
        if (node.left == null && node.right == null) {          // leaf reached
15
            // Emit the leaf's character — only leaves carry real data.
16
            out.append(node.data);
17
            node = root;                                        // reset for next code
18
        }
19
    }
20
    System.out.println(out.toString());
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(L) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6s with a single 1-bit codeword — One turn to a leaf → emit one character.Explore edge cases

Edge cases handled

s with a single 1-bit codewordOne turn to a leaf → emit one character.
Two codewords back to back (e.g. 0001)Reset after the first leaf lets the second codeword start cleanly.
Tree with a single leaf (one distinct char)Each bit lands on the lone leaf; emit and reset every bit.

Pitfalls

Not resetting to the root after an emit — descends off a leaf and crashes or garbles output.
Emitting at internal nodes — their data is a placeholder, not a character.
Swapping the 0=left / 1=right convention — decodes to the wrong characters.

03.2

Approach 2 of 2

Prefix-Table Decode — Build code→char Map First

TimeO(L + N)SpaceO(N)

Offer as an alternative or when you'll decode many strings against the same tree and want a reusable lookup.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Traverse the tree once, accumulating the path ('0'/'1') to each leaf, to build a code→character dictionary.

2Hint 2Explore hint

Then scan the encoded string, accumulating bits until the running prefix matches a code in the dictionary.

3Hint 3Explore hint

Because codes are prefix-free, the first match is unambiguous — emit, clear the buffer, and continue.

A · Core idea

Instead of walking the tree per bit, precompute the dictionary once and then match prefixes in the string.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

Tree A='1', B='00', C='01'; s = "0001"

Codebook from the tree

How to read it:DFS paths to leaves: A='1', B='00', C='01'.

Rendering diagram…

Final resultBC

C · Code with teaching comments

solution.javaJava

Prefix-Table Decode — Build code→char Map First — reference

4 teaching notes

1
import java.util.*;
2
 
3
Map<String, Character> buildCodes(Node node, String path, Map<String, Character> map) {
4
    if (node == null) return map;
5
    if (node.left == null && node.right == null) {   // leaf
6
        map.put(path.isEmpty() ? "0" : path, node.data);
7
        return map;
8
    }
9
    // Left edge contributes a '0' to the codeword.
10
    buildCodes(node.left, path + "0", map);
11
    buildCodes(node.right, path + "1", map);
12
    return map;
13
}
14
 
15
void decode(String s, Node root) {
16
    Map<String, Character> codes = buildCodes(root, "", new HashMap<>());
17
    StringBuilder out = new StringBuilder();
18
    StringBuilder buf = new StringBuilder();
19
    for (int i = 0; i < s.length(); i++) {
20
        buf.append(s.charAt(i));
21
        // Check if the current bit buffer exactly matches a codeword.
22
        Character c = codes.get(buf.toString());
23
        if (c != null) {                              // prefix-free → first match is final
24
            out.append(c);
25
            buf.setLength(0);
26
        }
27
    }
28
    System.out.println(out.toString());
29
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.29 lines

D · Why it works and complexityO(L + N) timeO(N) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6Single-leaf tree — Path is empty; guard it to a placeholder code like '0' so the lookup works.Explore edge cases

Edge cases handled

Single-leaf treePath is empty; guard it to a placeholder code like '0' so the lookup works.
Many strings, same treeBuild the map once, reuse it — this is when the table beats the walk.
Empty encoded stringNo bits → empty output.

Pitfalls

Building the map for every decode call when the tree is reused — wastes the table's advantage.
Not clearing the buffer after a match — concatenates codes and never matches again.
Mishandling the single-leaf empty-path case.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a Huffman tree node. class Node { int freq; char data; // meaningful only at leaves Node left;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

No reset after emitting

After hitting a leaf you must restart at the root. Without the reset the pointer tries to descend from a childless leaf — a null move (crash) or garbage on subsequent bits.

Explore the code comparison

Don't write this

for bit in s:
    node = node.left if bit == '0' else node.right
    if node.left is None and node.right is None:
        out.append(node.data)
        # missing: node = root  -> next bit derefs a leaf's null child

Write this instead

for bit in s:
    node = node.left if bit == '0' else node.right
    if node.left is None and node.right is None:
        out.append(node.data)
        node = root   # restart the next codeword from the top

Emitting at internal nodes

Internal nodes are structural and their data field is a placeholder. Emitting there produces placeholder characters in the output; only leaves hold real data.

Explore the code comparison

Don't write this

node = (bit == '0') ? node.left : node.right;
out.append(node.data);   // wrong: appends even at internal nodes

Write this instead

node = (bit == '0') ? node.left : node.right;
if (node.left == null && node.right == null) {  // only at leaves
    out.append(node.data);
    node = root;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Walk the Huffman tree per bit; emit at each leaf, reset to root

Code pattern to memorize

node = root
for bit in s:
    node = node.left if bit == '0' else node.right
    if node is a leaf:
        emit(node.data)
        node = root

Rules to remember

1'0' goes left, '1' goes right — the convention the tree was built with.
2A node is a leaf when both children are null; only leaves carry real characters.
3On reaching a leaf, emit its character and reset to the root for the next codeword.
4Huffman codes are prefix-free, so a leaf is reached at exactly one unambiguous point — no backtracking.
5Don't try to emit at internal nodes; their data is a placeholder, not an output character.

Use this pattern when

Decoding a bit stream against a known prefix-code (Huffman) tree
Any decode where the dictionary is structured as a trie/binary tree
Walking a tree driven by an external sequence of left/right instructions

Choose another pattern when

You must BUILD the Huffman tree from frequencies → that's the encoding/priority-queue problem, not this
Codes are fixed-length → index directly, no tree walk needed
Codes are not prefix-free → tree decoding is ambiguous; a different scheme is required

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Build a Huffman Tree (Encoding)
Coming soon
Use a min-heap of frequencies; repeatedly merge the two lowest into a parent node.
Implement Trie (Prefix Tree)
Coming soon
Same idea generalized: walk a trie driven by characters instead of bits.
Tree: Preorder Traversal
Building the code table is a preorder DFS accumulating the path.
Tree: Level Order Traversal
Another externally-driven tree walk, by level instead of by bit.

Same pattern

←

Tree: Height of a Binary Tree

Continue · Next problem

Tree: Inorder Traversal