DSA-081 · FOCUSED PRACTICE
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.
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.
No unsaved text changes · 154/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
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.
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
- T0
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.
| 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.
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
- T0
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.
| 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.
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.
| 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 depthNo invented null nodes in output.
Input:
100,000-node chain
Output:100,000 independent one-value rowsExplicit 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.