DSA-081 · Freeze the current BFS frontier before adding the next level

Binary Tree Level Order Traversal

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 23498 deterministic checks. Learner drafts are not executed.

Understand the problem

Return node values grouped by depth, top to bottom and left to right within each level.

Input roots are null or finite proper binary trees with at most 100,000 nodes per tree: no cycles and no shared child within one tree. Values span the full int domain. Structure/size are preconditions, not an extra validation traversal.
Preserve every original value, node identity, and left/right edge. Compact level-order arrays in examples are adapters, consuming two child slots per nonnull queued parent; they are not heap-indexed arrays.
Return a fresh mutable outer List and a distinct fresh mutable inner List for each depth. Empty input returns an empty list. Repeated calls share no mutable list objects. Integer values are immutable and may be boxed/cached.

Examples

Input: [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Children of earlier parents enter the FIFO first; left enters before right.
Input: [1,null,2,null,3]
Output: [[1],[2],[3]]
One value per level on a chain; queue size is not tree height.

Before you start

FIFO queues and proper binary tree structure
Depth versus frontier width and fresh nested outputs

Recognize the structure

Breadth-first traversal already visits nondecreasing depth. The extra requirement is to mark exactly where one depth ends even as children enter the queue.

Try before revealing

Hint 1

A queue visits nodes in nondecreasing depth.

Hint 2

How many nodes belong to the level before you enqueue any children?

Hint 3

Capture that count, remove exactly that many, then store the fresh row.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

DFS with explicit depth-indexed result rows

Recursively visit root, then left and right with depth+1. Create a row on first reaching a depth and append there. On [1,2,3,4], DFS visits 1,2,4,3 but records [[1],[2,3],[4]]. This is O(n) work and O(h) recursion; BFS avoids deep recursion and makes whole-level boundaries explicit.

Improve the baseline

Seed a nonnull root only

Create the fresh result first. Empty input returns it without enqueuing null.

Capture the current level count

At each outer iteration, count=queue.size() is the number of unprocessed nodes at exactly this depth. Process exactly count removals; children do not increase this loop bound.

Append left before right

For each removed parent append its value and enqueue nonnull left then right. Store the completed fresh row only after the fixed-size loop.

Why it is correct

Frontier invariant

Before a level begins, the queue contains exactly that level’s nodes in left-to-right order.

Preserve order and separation

Removing the captured count visits only that level. Their children arrive after all current nodes and are ordered first by parent position, then by left/right side.

Complete output

Each proper-tree node has one parent and enters once. When the queue empties every depth row is complete and the returned order satisfies both requirements.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    public static final class Node {
        public final int value;
        public Node left, right;
        public Node(int value) { this.value = value; }
    }
    public static List<List<Integer>> levels(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        ArrayDeque<Node> queue = new ArrayDeque<>();
        queue.addLast(root);
        while (!queue.isEmpty()) {
            int count = queue.size();
            List<Integer> level = new ArrayList<>(count);
            for (int i = 0; i < count; i++) {
                Node node = queue.removeFirst();
                level.add(node.value);
                if (node.left != null) queue.addLast(node.left);
                if (node.right != null) queue.addLast(node.right);
            }
            result.add(level);
        }
        return result;
    }
    private static void visit(Node node, int depth, List<List<Integer>> result) {
        if (node == null) return;
        if (depth == result.size()) result.add(new ArrayList<>());
        result.get(depth).add(node.value);
        visit(node.left,depth+1,result); visit(node.right,depth+1,result);
    }
    public static List<List<Integer>> baseline(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        visit(root,0,result); return result;
    }
}

Read the meaningful blocks

Snapshot size once

Re-reading queue.size() in a loop condition confuses removed parents with newly added children.

Allocate a row per level

Clearing and reusing one list would mutate earlier result rows.

Separate queue space from output

The queue can temporarily contain a current-level suffix plus the next-level prefix; this remains O(w), not exactly one frozen level at every instruction.

Complexity

Main traversal takes O(n) time and O(w) auxiliary queue space, where w is maximum level width; returned lists contain O(n) boxed values/references plus O(h) row objects, all counted as output. A chain uses a constant-size queue but n result rows.

The DFS baseline takes O(n) time with O(h) call frames excluding its output, and is restricted to shallow inputs. Neither traversal order is universally smaller in auxiliary memory.

Exact-state walkthroughs

Reveal normal and boundary traces

Freeze level size before adding children

Input: [3,9,20,null,null,15,7] · Result: [[3],[9,20],[15,7]]

Step 1 of 13: Seed the FIFO with the nonnull root only.

Queue order is front to back; completed rows and the current row are separate fresh lists.

Level order — fixed current-level boundary

Phase: initial. Current identity: null.

Original objects — unchanged source edges

T0: 3left → T1right → T2
T1: 9left → nullright → null
T2: 20left → T3right → T4
T3: 15left → nullright → null
T4: 7left → nullright → null

Captured level size: 0. Processed from that level: 0. Children entering the queue do not enlarge this loop bound.

FIFO — front at left

Current fresh level row

Empty.

Completed output rows — top to bottom

Empty.

The FIFO can contain a current-level suffix and a next-level prefix at once. Completed rows are returned output, not queue workspace.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]`
root	`"T0"`
queue	`["T0"]`
levels	`[]`
row	`[]`
count	`0`
processed	`0`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     public static List<List<Integer>> levels(Node root) {
 9         List<List<Integer>> result = new ArrayList<>();
10         if (root == null) return result;
11         ArrayDeque<Node> queue = new ArrayDeque<>();
12         queue.addLast(root);
13         while (!queue.isEmpty()) {
14             int count = queue.size();
15             List<Integer> level = new ArrayList<>(count);
16             for (int i = 0; i < count; i++) {
17                 Node node = queue.removeFirst();
18                 level.add(node.value);
19                 if (node.left != null) queue.addLast(node.left);
20                 if (node.right != null) queue.addLast(node.right);
21             }
22             result.add(level);
23         }
24         return result;
25     }
26     private static void visit(Node node, int depth, List<List<Integer>> result) {
27         if (node == null) return;
28         if (depth == result.size()) result.add(new ArrayList<>());
29         result.get(depth).add(node.value);
30         visit(node.left,depth+1,result); visit(node.right,depth+1,result);
31     }
32     public static List<List<Integer>> baseline(Node root) {
33         List<List<Integer>> result = new ArrayList<>();
34         visit(root,0,result); return result;
35     }
36 }
37

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed the FIFO with the nonnull root only.
Queue order is front to back; completed rows and the current row are separate fresh lists.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
queue
["T0"]
levels
[]
row
[]
count
0
processed
0
phase
"initial"
current
null
Freeze the number of nodes belonging to this level.
Exactly count removals belong to this row; later children do not change that bound.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
queue
["T0"]
levels
[]
row
[]
count
1
processed
0
phase
"begin-level"
current
null
Emit one current-level value and append its children.
The queue may mix the current-level suffix with the next-level prefix; only count−processed current nodes remain.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
queue
["T1","T2"]
levels
[]
row
[3]
count
1
processed
1
phase
"visit"
current
"T0"
Store this completed independent depth row.
Rows are top-down and left-to-right. Teaching history copies are not additional Java traversal state.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
queue
["T1","T2"]
levels
[[3]]
row
[3]
count
1
processed
1
phase
"finish-level"
current
null
Freeze the number of nodes belonging to this level.
Exactly count removals belong to this row; later children do not change that bound.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
queue
["T1","T2"]
levels
[[3]]
row
[]
count
2
processed
0
phase
"begin-level"
current
null
Emit one current-level value and append its children.
The queue may mix the current-level suffix with the next-level prefix; only count−processed current nodes remain.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
queue
["T2"]
levels
[[3]]
row
[9]
count
2
processed
1
phase
"visit"
current
"T1"
Emit one current-level value and append its children.
The queue may mix the current-level suffix with the next-level prefix; only count−processed current nodes remain.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
queue
["T3","T4"]
levels
[[3]]
row
[9,20]
count
2
processed
2
phase
"visit"
current
"T2"
Store this completed independent depth row.
Rows are top-down and left-to-right. Teaching history copies are not additional Java traversal state.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
queue
["T3","T4"]
levels
[[3],[9,20]]
row
[9,20]
count
2
processed
2
phase
"finish-level"
current
null
Freeze the number of nodes belonging to this level.
Exactly count removals belong to this row; later children do not change that bound.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
queue
["T3","T4"]
levels
[[3],[9,20]]
row
[]
count
2
processed
0
phase
"begin-level"
current
null
Emit one current-level value and append its children.
The queue may mix the current-level suffix with the next-level prefix; only count−processed current nodes remain.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
queue
["T4"]
levels
[[3],[9,20]]
row
[15]
count
2
processed
1
phase
"visit"
current
"T3"
Emit one current-level value and append its children.
The queue may mix the current-level suffix with the next-level prefix; only count−processed current nodes remain.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
queue
[]
levels
[[3],[9,20]]
row
[15,7]
count
2
processed
2
phase
"visit"
current
"T4"
Store this completed independent depth row.
Rows are top-down and left-to-right. Teaching history copies are not additional Java traversal state.
treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]
root
"T0"
queue
[]
levels
[[3],[9,20],[15,7]]
row
[15,7]
count
2
processed
2
phase
"finish-level"
current
null
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
[[3],[9,20],[15,7]]

A chain has narrow queue but many levels

Input: [1,null,2,null,3] · Result: [[1],[2],[3]]

Step 1 of 11: Seed the FIFO with the nonnull root only.

Queue order is front to back; completed rows and the current row are separate fresh lists.

Level order — fixed current-level boundary

Phase: initial. Current identity: null.

Original objects — unchanged source edges

T0: 1left → nullright → T1
T1: 2left → nullright → T2
T2: 3left → nullright → null

Captured level size: 0. Processed from that level: 0. Children entering the queue do not enlarge this loop bound.

FIFO — front at left

Current fresh level row

Empty.

Completed output rows — top to bottom

Empty.

The FIFO can contain a current-level suffix and a next-level prefix at once. Completed rows are returned output, not queue workspace.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":1,"left":null,"right":"T1"},{"id":"T1","value":2,"left":null,"right":"T2"},{"id":"T2","value":3,"left":null,"right":null}]`
root	`"T0"`
queue	`["T0"]`
levels	`[]`
row	`[]`
count	`0`
processed	`0`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     public static List<List<Integer>> levels(Node root) {
 9         List<List<Integer>> result = new ArrayList<>();
10         if (root == null) return result;
11         ArrayDeque<Node> queue = new ArrayDeque<>();
12         queue.addLast(root);
13         while (!queue.isEmpty()) {
14             int count = queue.size();
15             List<Integer> level = new ArrayList<>(count);
16             for (int i = 0; i < count; i++) {
17                 Node node = queue.removeFirst();
18                 level.add(node.value);
19                 if (node.left != null) queue.addLast(node.left);
20                 if (node.right != null) queue.addLast(node.right);
21             }
22             result.add(level);
23         }
24         return result;
25     }
26     private static void visit(Node node, int depth, List<List<Integer>> result) {
27         if (node == null) return;
28         if (depth == result.size()) result.add(new ArrayList<>());
29         result.get(depth).add(node.value);
30         visit(node.left,depth+1,result); visit(node.right,depth+1,result);
31     }
32     public static List<List<Integer>> baseline(Node root) {
33         List<List<Integer>> result = new ArrayList<>();
34         visit(root,0,result); return result;
35     }
36 }
37

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed the FIFO with the nonnull root only.
Queue order is front to back; completed rows and the current row are separate fresh lists.
treeNodes
[{"id":"T0","value":1,"left":null,"right":"T1"},{"id":"T1","value":2,"left":null,"right":"T2"},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
queue
["T0"]
levels
[]
row
[]
count
0
processed
0
phase
"initial"
current
null
Freeze the number of nodes belonging to this level.
Exactly count removals belong to this row; later children do not change that bound.
treeNodes
[{"id":"T0","value":1,"left":null,"right":"T1"},{"id":"T1","value":2,"left":null,"right":"T2"},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
queue
["T0"]
levels
[]
row
[]
count
1
processed
0
phase
"begin-level"
current
null
Emit one current-level value and append its children.
The queue may mix the current-level suffix with the next-level prefix; only count−processed current nodes remain.
treeNodes
[{"id":"T0","value":1,"left":null,"right":"T1"},{"id":"T1","value":2,"left":null,"right":"T2"},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
queue
["T1"]
levels
[]
row
[1]
count
1
processed
1
phase
"visit"
current
"T0"
Store this completed independent depth row.
Rows are top-down and left-to-right. Teaching history copies are not additional Java traversal state.
treeNodes
[{"id":"T0","value":1,"left":null,"right":"T1"},{"id":"T1","value":2,"left":null,"right":"T2"},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
queue
["T1"]
levels
[[1]]
row
[1]
count
1
processed
1
phase
"finish-level"
current
null
Freeze the number of nodes belonging to this level.
Exactly count removals belong to this row; later children do not change that bound.
treeNodes
[{"id":"T0","value":1,"left":null,"right":"T1"},{"id":"T1","value":2,"left":null,"right":"T2"},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
queue
["T1"]
levels
[[1]]
row
[]
count
1
processed
0
phase
"begin-level"
current
null
Emit one current-level value and append its children.
The queue may mix the current-level suffix with the next-level prefix; only count−processed current nodes remain.
treeNodes
[{"id":"T0","value":1,"left":null,"right":"T1"},{"id":"T1","value":2,"left":null,"right":"T2"},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
queue
["T2"]
levels
[[1]]
row
[2]
count
1
processed
1
phase
"visit"
current
"T1"
Store this completed independent depth row.
Rows are top-down and left-to-right. Teaching history copies are not additional Java traversal state.
treeNodes
[{"id":"T0","value":1,"left":null,"right":"T1"},{"id":"T1","value":2,"left":null,"right":"T2"},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
queue
["T2"]
levels
[[1],[2]]
row
[2]
count
1
processed
1
phase
"finish-level"
current
null
Freeze the number of nodes belonging to this level.
Exactly count removals belong to this row; later children do not change that bound.
treeNodes
[{"id":"T0","value":1,"left":null,"right":"T1"},{"id":"T1","value":2,"left":null,"right":"T2"},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
queue
["T2"]
levels
[[1],[2]]
row
[]
count
1
processed
0
phase
"begin-level"
current
null
Emit one current-level value and append its children.
The queue may mix the current-level suffix with the next-level prefix; only count−processed current nodes remain.
treeNodes
[{"id":"T0","value":1,"left":null,"right":"T1"},{"id":"T1","value":2,"left":null,"right":"T2"},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
queue
[]
levels
[[1],[2]]
row
[3]
count
1
processed
1
phase
"visit"
current
"T2"
Store this completed independent depth row.
Rows are top-down and left-to-right. Teaching history copies are not additional Java traversal state.
treeNodes
[{"id":"T0","value":1,"left":null,"right":"T1"},{"id":"T1","value":2,"left":null,"right":"T2"},{"id":"T2","value":3,"left":null,"right":null}]
root
"T0"
queue
[]
levels
[[1],[2],[3]]
row
[3]
count
1
processed
1
phase
"finish-level"
current
null
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
[[1],[2],[3]]

Fresh empty output

Input: [] · Result: []

Step 1 of 2: Seed the FIFO with the nonnull root only.

Queue order is front to back; completed rows and the current row are separate fresh lists.

Level order — fixed current-level boundary

Phase: initial. Current identity: null.

Original objects — unchanged source edges

Empty tree.

Captured level size: 0. Processed from that level: 0. Children entering the queue do not enlarge this loop bound.

FIFO — front at left

Empty.

Current fresh level row

Empty.

Completed output rows — top to bottom

Empty.

The FIFO can contain a current-level suffix and a next-level prefix at once. Completed rows are returned output, not queue workspace.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
Variable	Value
treeNodes	`[]`
root	`null`
queue	`[]`
levels	`[]`
row	`[]`
count	`0`
processed	`0`
phase	`"initial"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     public static List<List<Integer>> levels(Node root) {
 9         List<List<Integer>> result = new ArrayList<>();
10         if (root == null) return result;
11         ArrayDeque<Node> queue = new ArrayDeque<>();
12         queue.addLast(root);
13         while (!queue.isEmpty()) {
14             int count = queue.size();
15             List<Integer> level = new ArrayList<>(count);
16             for (int i = 0; i < count; i++) {
17                 Node node = queue.removeFirst();
18                 level.add(node.value);
19                 if (node.left != null) queue.addLast(node.left);
20                 if (node.right != null) queue.addLast(node.right);
21             }
22             result.add(level);
23         }
24         return result;
25     }
26     private static void visit(Node node, int depth, List<List<Integer>> result) {
27         if (node == null) return;
28         if (depth == result.size()) result.add(new ArrayList<>());
29         result.get(depth).add(node.value);
30         visit(node.left,depth+1,result); visit(node.right,depth+1,result);
31     }
32     public static List<List<Integer>> baseline(Node root) {
33         List<List<Integer>> result = new ArrayList<>();
34         visit(root,0,result); return result;
35     }
36 }
37

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed the FIFO with the nonnull root only.
Queue order is front to back; completed rows and the current row are separate fresh lists.
treeNodes
[]
root
null
queue
[]
levels
[]
row
[]
count
0
processed
0
phase
"initial"
current
null
Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
result
[]

Test the contract

Input: null
Output: []
Fresh empty outer list.
Input: [1,2,3]
Output: [[1],[2,3]]
Parent and side order.
Input: Sparse tree with duplicate values
Output: one row per actual depth
No invented null nodes in output.
Input: 100,000-node chain
Output: 100,000 independent one-value rows
Explicit queue supports full depth.

Common mistakes and counterexamples

Use the changing queue size as a loop bound

Counterexample: Children can be consumed into the same row or later current nodes skipped.

Capture count before processing the level.

Reuse the same inner list

Counterexample: Adding later values changes every stored alias.

Create a distinct list each outer iteration.

Enqueue right before left

Counterexample: [1,2,3] becomes [[1],[3,2]].

Preserve parent order and left-before-right enqueue order.

Follow-ups

Produce zigzag rows.

Keep BFS order internally and place values at opposite row indices on alternate depths, or reverse completed rows. Avoid front insertion into ArrayList, which can make a wide level quadratic.

Return the right-side view.

Record the final node from each captured level. This changes output size to O(h), not traversal work.

Stream levels to a consumer.

Emit a completed row and release it if the consumer permits. The consumer’s retention is separate from traversal memory; define whether it may mutate or retain each row.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 154/20,000 characters

Self-review

Can I prove the captured count excludes newly queued children?Can I distinguish O(w) traversal state from O(n) output?Can I demonstrate independent mutable rows across depths and calls?

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform equivalence claims.