Loading…

mediumTreesLC #102Asked very often

Binary Tree Level Order Traversal

Q: How do you solve Binary Tree Level Order Traversal using the DFS with Depth Index approach?

When to use it: Offer it as the recursive alternative: it produces the same grouped output and uses only O(h) stack space instead of an O(width) queue. You don't strictly need a queue to group by level — a depth-carrying DFS works too. The key is that a node's depth tells you exactly which output row it belongs to. **How the grouping happens.** We recurse pre-order (node, then left, then right) while tracking the current `depth`. The first time we reach a given depth, we append a fresh empty list to `result`. Because we always recurse left before right, values land in each row in left-to-right order automatically. **Why left-before-right matters.** DFS doesn't visit a level contiguously — it dives all the way down the left spine first. But within any single depth, the left subtree's nodes are always reached before the right subtree's, so the per-row ordering still comes out left-to-right. **Space trade-off vs BFS.** DFS holds at most one root-to-leaf path on the stack, O(h). BFS holds an entire level in the queue, O(width). For a balanced tree the widest level is ~n/2, so DFS can be more memory-friendly on tall trees, while BFS is more natural when the problem is fundamentally about levels. Time complexity: O(n). Space complexity: O(h).

Q: How do you solve Binary Tree Level Order Traversal using the BFS with a Queue — Level by Level (Optimal) approach?

When to use it: The canonical answer. Lead with 'level order means BFS with a queue', then explain the size-snapshot trick. BFS is the textbook fit for 'process nearest-first', and a FIFO queue gives that ordering for free. The only added requirement here is grouping the output by depth, which the size-snapshot handles. **The size-snapshot trick.** When we start a level, the queue contains exactly the nodes of that level and nothing else. We read `levelSize = queue.size()` once, then dequeue precisely that many nodes. As we dequeue each, we enqueue its children — but those children belong to the *next* level, and since we loop a fixed `levelSize` times, they aren't touched until the next round. This cleanly walls off one level from the next without storing a depth on each node. **Why the snapshot must come before the loop.** If you re-read `queue.size()` inside the loop condition, the size grows as you append children, and the current level's sub-list absorbs nodes from deeper levels. Capturing the size up front freezes the boundary. **Why a real queue matters.** We need O(1) removal from the front. In Python use `collections.deque` (`popleft` is O(1)); a plain list's `pop(0)` is O(n) and silently makes the whole traversal O(n²). In Java, `ArrayDeque` / `LinkedList` via the `Queue` interface gives O(1) `poll`. **Handling the empty tree.** A null root means no levels at all. Guard it before the loop — enqueuing null and later dereferencing it is a classic crash. Time complexity: O(n). Space complexity: O(n).

LCPractice

Trees & BST · 9 of 41 · 8 min

Given the root of a binary tree, return **the level order traversal** of its nodes' values. (i.e., from left to right, level by level).

The result is a list of lists: the i-th inner list contains all node values at depth i, ordered left to right.

In plain English

Produce the node values grouped by depth: row 0 is just the root, row 1 is its children left-to-right, and so on. We need a traversal that fans out one layer at a time and a way to know where each layer ends.

Examples

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Note: Depth 0 is [3]; depth 1 is [9,20]; depth 2 is the children of 20, namely [15,7].

Example 2

Input: root = [1]
Output: [[1]]
Note: A single node forms one level.

Example 3

Input: root = []
Output: []
Note: Empty tree → no levels.

Constraints

The number of nodes is in the range [0, 2000]
-1000 ≤ Node.val ≤ 1000
The tree may be empty (root == null)

Clarifying questions4First question: Can the tree be empty?Explore questions

Q1.Can the tree be empty?
Yes — constraints allow 0 nodes. Return an empty list, and don't enqueue a null root.
Q2.Left-to-right within each level, or any order?
Left-to-right. Enqueue the left child before the right child so the queue preserves that order.
Q3.Do you want a flat list or a list grouped by level?
Grouped — one inner list per depth. That's why we batch by the level size each round.
Q4.How large can the tree get?
Up to 2000 nodes here, but the BFS approach scales to any size in O(n); the widest level bounds the queue size.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Breadth-first search with a queue, processing the tree one level at a time. Before each round, snapshot the queue's current size — that's exactly how many nodes are on this level. Dequeue that many, collect their values into a sub-list, and enqueue their children for the next round. O(n) time, O(n) space. The 'capture the level size up front' trick is what cleanly groups nodes by depth.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know BFS uses a queue, and whether you can cleanly separate one level from the next using the queue-size snapshot rather than tagging nodes with depth.

Where candidates slip

Reading `len(queue)` inside the loop (so children get counted into the current level), or using `list.pop(0)` and quietly turning the traversal into O(n²).

How to stand out

State the level-size trick explicitly, handle the empty tree first, and mention the DFS-with-depth alternative that produces the same grouping in O(h) stack space.

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	DFS with Depth Index	`O(n)`	`O(h)`	Offer it as the recursive alternative: it produces the same grouped output and uses only O(h) stack space instead of an O(width) queue.	Read
2	BFS with a Queue — Level by Level (Optimal)Optimal	`O(n)`	`O(n)`	The canonical answer. Lead with 'level order means BFS with a queue', then explain the size-snapshot trick.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewTraverse a binary treeGroup output by level/depth?YesNoExplore the full tree

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

DFS with Depth Index

TimeO(n)SpaceO(h)

Offer it as the recursive alternative: it produces the same grouped output and uses only O(h) stack space instead of an O(width) queue.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Could you recurse normally but also pass down which level you're on?

2Hint 2Explore hint

Carry a `depth` argument. The node at `depth` belongs in `result[depth]`.

3Hint 3Explore hint

If `result` doesn't yet have a list at index `depth`, create one, then append the node's value and recurse into both children with `depth + 1`.

A · Core idea

You don't strictly need a queue to group by level — a depth-carrying DFS works too. The key is that a node's depth tells you exactly which output row it belongs to.

How the grouping happens. We recurse pre-order (node, then left, then right) while tracking the current depth. The first time we reach a given depth, we append a fresh empty list to result. Because we always recurse left before right, values land in each row in left-to-right order automatically.

Why left-before-right matters. DFS doesn't visit a level contiguously — it dives all the way down the left spine first. But within any single depth, the left subtree's nodes are always reached before the right subtree's, so the per-row ordering still comes out left-to-right.

Space trade-off vs BFS. DFS holds at most one root-to-leaf path on the stack, O(h). BFS holds an entire level in the queue, O(width). For a balanced tree the widest level is ~n/2, so DFS can be more memory-friendly on tall trees, while BFS is more natural when the problem is fundamentally about levels.

B · Visual dry run

Interactive dry run

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

root = [3,9,20,null,null,15,7]

visit 3, depth 0

create result[0], append 3

Stateresult = [[3]]

Final result[[3],[9,20],[15,7]]

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the full code

solution.javaJava

DFS with Depth Index — reference

3 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
public List<List<Integer>> levelOrder(TreeNode root) {
9
    List<List<Integer>> result = new ArrayList<>();
10
    dfs(root, 0, result);
11
    return result;
12
}
13
 
14
private void dfs(TreeNode node, int depth, List<List<Integer>> result) {
15
    if (node == null) {
16
        return;
17
    }
18
    // First time we reach this depth → create its row before appending.
19
    if (depth == result.size()) {
20
        result.add(new ArrayList<>());
21
    }
22
    // Map the node to its level by index — depth is the row key.
23
    result.get(depth).add(node.val);
24
    // Left before right keeps each row in left-to-right order.
25
    dfs(node.left, depth + 1, result);
26
    dfs(node.right, depth + 1, result);
27
}

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

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

The depth argument is the whole trick: it's a stable key that maps each node to its output row regardless of visitation order. This 'pass an accumulator/index down the recursion' technique generalizes to many tree problems.

ComplexityO(n) time, O(h) space — Every node is visited once → O(n). The recursion stack reaches the tree's height → O(h), better than BFS's O(width) for tall, narrow trees (ignoring the output list itself).

E · Edge cases and pitfalls3Recursing right before left — scrambles the within-level order.Explore edge cases

Pitfalls

Recursing right before left — scrambles the within-level order.
Forgetting to create result[depth] the first time, causing an index error.
Assuming DFS visits levels contiguously — it doesn't, but the depth index still groups correctly.

03.2

Approach 2 of 2 · Optimal

BFS with a Queue — Level by Level (Optimal)

TimeO(n)SpaceO(n)

The canonical answer. Lead with 'level order means BFS with a queue', then explain the size-snapshot trick.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Level order means visiting nodes nearest the root first. What data structure gives you first-in-first-out exploration?

2Hint 2Explore hint

Push the root, then repeatedly process the queue. The trick: how do you know where one level ends and the next begins?

3Hint 3Explore hint

Before processing a level, record how many nodes are currently in the queue — that count is the size of the current level. Pop exactly that many, collecting values, and enqueue their children for next time.

A · Core idea

BFS is the textbook fit for 'process nearest-first', and a FIFO queue gives that ordering for free. The only added requirement here is grouping the output by depth, which the size-snapshot handles.

The size-snapshot trick. When we start a level, the queue contains exactly the nodes of that level and nothing else. We read levelSize = queue.size() once, then dequeue precisely that many nodes. As we dequeue each, we enqueue its children — but those children belong to the next level, and since we loop a fixed levelSize times, they aren't touched until the next round. This cleanly walls off one level from the next without storing a depth on each node.

Why the snapshot must come before the loop. If you re-read queue.size() inside the loop condition, the size grows as you append children, and the current level's sub-list absorbs nodes from deeper levels. Capturing the size up front freezes the boundary.

Why a real queue matters. We need O(1) removal from the front. In Python use collections.deque (popleft is O(1)); a plain list's pop(0) is O(n) and silently makes the whole traversal O(n²). In Java, ArrayDeque / LinkedList via the Queue interface gives O(1) poll.

Handling the empty tree. A null root means no levels at all. Guard it before the loop — enqueuing null and later dereferencing it is a classic crash.

B · Visual dry run

Interactive dry run

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

root = [3,9,20,null,null,15,7]

Interactive diagram

Levels of the example tree

level 0

Active call / nodeSupporting contextReturned stateNot active

BFS emits one row per depth: [3], then [9,20], then [15,7].

Final result[[3],[9,20],[15,7]]

C · Code with teaching comments

solution.javaJava

BFS with a Queue — Level by Level (Optimal) — optimal

4 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
public List<List<Integer>> levelOrder(TreeNode root) {
9
    List<List<Integer>> result = new ArrayList<>();
10
    // Empty tree → no levels; return the empty result before touching the queue.
11
    if (root == null) {
12
        return result;
13
    }
14
    Queue<TreeNode> queue = new LinkedList<>();
15
    queue.offer(root);
16
    while (!queue.isEmpty()) {
17
        // Snapshot the level boundary BEFORE adding children — the heart of the
18
        // algorithm.
19
        int levelSize = queue.size();
20
        List<Integer> level = new ArrayList<>();
21
        // Drain exactly one level; children enqueued here belong to the next round.
22
        for (int i = 0; i < levelSize; i++) {
23
            TreeNode node = queue.poll();
24
            level.add(node.val);
25
            // Left before right preserves left-to-right level order.
26
            if (node.left != null) queue.offer(node.left);
27
            if (node.right != null) queue.offer(node.right);
28
        }
29
        result.add(level);
30
    }
31
    return result;
32
}

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

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

The queue size at the top of each iteration is a free 'level marker'. You don't need to tag nodes with their depth or push sentinels — the count of what's already enqueued is the level boundary. This single observation powers zigzag traversal, right-side view, and level averages with almost no change.

ComplexityO(n) time, O(n) space — Each node is enqueued and dequeued exactly once and does O(1) work → O(n) time. The queue holds at most one level; the widest level can be ~n/2 nodes → O(n) space.

E · Edge cases and pitfalls6root = null — Guard returns [] immediately; the queue is never created.Explore edge cases

Edge cases handled

root = nullGuard returns [] immediately; the queue is never created.
root = [1]One round: size=1, pop 1, no children → result = [[1]].
Completely skewed tree (left spine of 2000 nodes)Each level has one node; 2000 rounds of size 1 → 2000 single-element rows, still O(n).

Pitfalls

Re-reading queue.size() inside the loop so children leak into the current level.
Using list.pop(0) in Python — O(n) per pop turns the traversal into O(n²).
Enqueuing a null root and then dereferencing it.

Practice

Try the solution yourself

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

Editable code preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;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.

Reading the level size inside the loop

The queue grows as you enqueue children, so a loop bounded by the live size keeps consuming next-level nodes into the current row, collapsing all levels into one.

Explore the code comparison

Don't write this

while queue:
    level = []
    while len(queue):            # grows as children are added!
        node = queue.popleft()
        level.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    result.append(level)

Write this instead

while queue:
    level = []
    for _ in range(len(queue)):  # size frozen before the loop
        node = queue.popleft()
        level.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    result.append(level)

Using a list as a queue

list.pop(0) shifts every remaining element left, costing O(n) each call. Over n nodes that's O(n²). A deque (Python) or ArrayDeque/LinkedList (Java) pops from the front in O(1).

Explore the code comparison

Don't write this

queue = [root]
while queue:
    node = queue.pop(0)   # O(n) each time → O(n^2) total

Write this instead

from collections import deque
queue = deque([root])
while queue:
    node = queue.popleft()  # O(1)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

BFS by level (snapshot the queue size)

Code pattern to memorize

queue = deque([root]) if root else deque()
while queue:
    level = []
    for _ in range(len(queue)):   # FIX size before looping
        node = queue.popleft()
        level.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    result.append(level)

Rules to remember

1Snapshot len(queue) before the inner loop — appending children mid-loop would otherwise bleed the next level into this one.
2Guard against a null root: return an empty list, don't enqueue null.
3Use a real queue/deque with O(1) pop-from-front, not list.pop(0) which is O(n).
4Enqueue children left before right so each level reads left-to-right.
5Each node is enqueued and dequeued exactly once → O(n) time; the queue can hold a full level → O(n) space.

Use this pattern when

You need results grouped by **depth / level** of the tree
Shortest-path-in-unweighted / 'nearest first' exploration order
Anything that asks for 'level', 'row', 'each layer', or 'breadth'
Zigzag, right-side view, level averages — all are BFS-by-level variants

Choose another pattern when

You only need a single value per level or just the last level → still BFS but lighter bookkeeping
Order doesn't matter and you just want all nodes → plain DFS is simpler
Tree is enormous and you only need depth → DFS recursion avoids the wide queue
You need pre/in/post order → that's DFS, not BFS

Interview takeaway

Level-order traversal is the canonical BFS-on-a-tree. The one idea that makes it click is fixing the level boundary by reading the queue size before you start dequeuing — every 'do something per level' tree problem (zigzag, right view, level averages, min depth) is a small twist on this skeleton.

Continue

Transfer the pattern to another problem

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

Transferable patternBFS by level with a queue. Reach for it whenever the answer is organized by depth. The 'snapshot the queue size before draining' skeleton is reused verbatim in zigzag traversal, right-side view, level averages, and minimum depth.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Binary Tree Level Order Traversal II
Coming soon
Same BFS, then reverse the result list (or prepend each level) for bottom-up order.
Binary Tree Zigzag Level Order Traversal
BFS by level, but reverse every other level's sub-list (or use a deque per row).
Binary Tree Right Side View
BFS by level and keep only the last node of each level.
Average of Levels in Binary Tree
Same level loop, but sum each level and divide by its size.

Same pattern

←

Lowest Common Ancestor of a BST

Continue · Next problem

Binary Tree Right Side View

mediumTreesLC #102Asked very often

Binary Tree Level Order Traversal

LCPractice

Trees & BST · 9 of 41 · 8 min

Given the root of a binary tree, return **the level order traversal** of its nodes' values. (i.e., from left to right, level by level).

The result is a list of lists: the i-th inner list contains all node values at depth i, ordered left to right.

In plain English

Examples

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Note: Depth 0 is [3]; depth 1 is [9,20]; depth 2 is the children of 20, namely [15,7].

Example 2

Input: root = [1]
Output: [[1]]
Note: A single node forms one level.

Example 3

Input: root = []
Output: []
Note: Empty tree → no levels.

Constraints

The number of nodes is in the range [0, 2000]
-1000 ≤ Node.val ≤ 1000
The tree may be empty (root == null)

Clarifying questions4First question: Can the tree be empty?Explore questions

Q1.Can the tree be empty?
Yes — constraints allow 0 nodes. Return an empty list, and don't enqueue a null root.
Q2.Left-to-right within each level, or any order?
Left-to-right. Enqueue the left child before the right child so the queue preserves that order.
Q3.Do you want a flat list or a list grouped by level?
Grouped — one inner list per depth. That's why we batch by the level size each round.
Q4.How large can the tree get?
Up to 2000 nodes here, but the BFS approach scales to any size in O(n); the widest level bounds the queue size.

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 know BFS uses a queue, and whether you can cleanly separate one level from the next using the queue-size snapshot rather than tagging nodes with depth.

Where candidates slip

Reading `len(queue)` inside the loop (so children get counted into the current level), or using `list.pop(0)` and quietly turning the traversal into O(n²).

How to stand out

State the level-size trick explicitly, handle the empty tree first, and mention the DFS-with-depth alternative that produces the same grouping in O(h) stack space.

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	DFS with Depth Index	`O(n)`	`O(h)`	Offer it as the recursive alternative: it produces the same grouped output and uses only O(h) stack space instead of an O(width) queue.	Read
2	BFS with a Queue — Level by Level (Optimal)Optimal	`O(n)`	`O(n)`	The canonical answer. Lead with 'level order means BFS with a queue', then explain the size-snapshot trick.	Read

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

DFS with Depth Index

TimeO(n)SpaceO(h)

Offer it as the recursive alternative: it produces the same grouped output and uses only O(h) stack space instead of an O(width) queue.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Could you recurse normally but also pass down which level you're on?

2Hint 2Explore hint

Carry a `depth` argument. The node at `depth` belongs in `result[depth]`.

3Hint 3Explore hint

If `result` doesn't yet have a list at index `depth`, create one, then append the node's value and recurse into both children with `depth + 1`.

A · Core idea

You don't strictly need a queue to group by level — a depth-carrying DFS works too. The key is that a node's depth tells you exactly which output row it belongs to.

B · Visual dry run

Interactive dry run

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

root = [3,9,20,null,null,15,7]

visit 3, depth 0

create result[0], append 3

Stateresult = [[3]]

Final result[[3],[9,20],[15,7]]

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the full code

solution.javaJava

DFS with Depth Index — reference

3 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
public List<List<Integer>> levelOrder(TreeNode root) {
9
    List<List<Integer>> result = new ArrayList<>();
10
    dfs(root, 0, result);
11
    return result;
12
}
13
 
14
private void dfs(TreeNode node, int depth, List<List<Integer>> result) {
15
    if (node == null) {
16
        return;
17
    }
18
    // First time we reach this depth → create its row before appending.
19
    if (depth == result.size()) {
20
        result.add(new ArrayList<>());
21
    }
22
    // Map the node to its level by index — depth is the row key.
23
    result.get(depth).add(node.val);
24
    // Left before right keeps each row in left-to-right order.
25
    dfs(node.left, depth + 1, result);
26
    dfs(node.right, depth + 1, result);
27
}

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

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Recursing right before left — scrambles the within-level order.Explore edge cases

Pitfalls

Recursing right before left — scrambles the within-level order.
Forgetting to create result[depth] the first time, causing an index error.
Assuming DFS visits levels contiguously — it doesn't, but the depth index still groups correctly.

03.2

Approach 2 of 2 · Optimal

BFS with a Queue — Level by Level (Optimal)

TimeO(n)SpaceO(n)

The canonical answer. Lead with 'level order means BFS with a queue', then explain the size-snapshot trick.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Level order means visiting nodes nearest the root first. What data structure gives you first-in-first-out exploration?

2Hint 2Explore hint

Push the root, then repeatedly process the queue. The trick: how do you know where one level ends and the next begins?

3Hint 3Explore hint

A · Core idea

BFS is the textbook fit for 'process nearest-first', and a FIFO queue gives that ordering for free. The only added requirement here is grouping the output by depth, which the size-snapshot handles.

Handling the empty tree. A null root means no levels at all. Guard it before the loop — enqueuing null and later dereferencing it is a classic crash.

B · Visual dry run

Interactive dry run

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

root = [3,9,20,null,null,15,7]

Interactive diagram

Levels of the example tree

level 0

Active call / nodeSupporting contextReturned stateNot active

BFS emits one row per depth: [3], then [9,20], then [15,7].

Final result[[3],[9,20],[15,7]]

C · Code with teaching comments

solution.javaJava

BFS with a Queue — Level by Level (Optimal) — optimal

4 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
public List<List<Integer>> levelOrder(TreeNode root) {
9
    List<List<Integer>> result = new ArrayList<>();
10
    // Empty tree → no levels; return the empty result before touching the queue.
11
    if (root == null) {
12
        return result;
13
    }
14
    Queue<TreeNode> queue = new LinkedList<>();
15
    queue.offer(root);
16
    while (!queue.isEmpty()) {
17
        // Snapshot the level boundary BEFORE adding children — the heart of the
18
        // algorithm.
19
        int levelSize = queue.size();
20
        List<Integer> level = new ArrayList<>();
21
        // Drain exactly one level; children enqueued here belong to the next round.
22
        for (int i = 0; i < levelSize; i++) {
23
            TreeNode node = queue.poll();
24
            level.add(node.val);
25
            // Left before right preserves left-to-right level order.
26
            if (node.left != null) queue.offer(node.left);
27
            if (node.right != null) queue.offer(node.right);
28
        }
29
        result.add(level);
30
    }
31
    return result;
32
}

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

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

E · Edge cases and pitfalls6root = null — Guard returns [] immediately; the queue is never created.Explore edge cases

Edge cases handled

root = nullGuard returns [] immediately; the queue is never created.
root = [1]One round: size=1, pop 1, no children → result = [[1]].
Completely skewed tree (left spine of 2000 nodes)Each level has one node; 2000 rounds of size 1 → 2000 single-element rows, still O(n).

Pitfalls

Re-reading queue.size() inside the loop so children leak into the current level.
Using list.pop(0) in Python — O(n) per pop turns the traversal into O(n²).
Enqueuing a null root and then dereferencing it.

Practice

Try the solution yourself

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

Editable code preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;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.

Reading the level size inside the loop

The queue grows as you enqueue children, so a loop bounded by the live size keeps consuming next-level nodes into the current row, collapsing all levels into one.

Explore the code comparison

Don't write this

while queue:
    level = []
    while len(queue):            # grows as children are added!
        node = queue.popleft()
        level.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    result.append(level)

Write this instead

while queue:
    level = []
    for _ in range(len(queue)):  # size frozen before the loop
        node = queue.popleft()
        level.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    result.append(level)

Using a list as a queue

list.pop(0) shifts every remaining element left, costing O(n) each call. Over n nodes that's O(n²). A deque (Python) or ArrayDeque/LinkedList (Java) pops from the front in O(1).

Explore the code comparison

Don't write this

queue = [root]
while queue:
    node = queue.pop(0)   # O(n) each time → O(n^2) total

Write this instead

from collections import deque
queue = deque([root])
while queue:
    node = queue.popleft()  # O(1)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

BFS by level (snapshot the queue size)

Code pattern to memorize

queue = deque([root]) if root else deque()
while queue:
    level = []
    for _ in range(len(queue)):   # FIX size before looping
        node = queue.popleft()
        level.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    result.append(level)

Rules to remember

1Snapshot len(queue) before the inner loop — appending children mid-loop would otherwise bleed the next level into this one.
2Guard against a null root: return an empty list, don't enqueue null.
3Use a real queue/deque with O(1) pop-from-front, not list.pop(0) which is O(n).
4Enqueue children left before right so each level reads left-to-right.
5Each node is enqueued and dequeued exactly once → O(n) time; the queue can hold a full level → O(n) space.

Use this pattern when

You need results grouped by **depth / level** of the tree
Shortest-path-in-unweighted / 'nearest first' exploration order
Anything that asks for 'level', 'row', 'each layer', or 'breadth'
Zigzag, right-side view, level averages — all are BFS-by-level variants

Choose another pattern when

You only need a single value per level or just the last level → still BFS but lighter bookkeeping
Order doesn't matter and you just want all nodes → plain DFS is simpler
Tree is enormous and you only need depth → DFS recursion avoids the wide queue
You need pre/in/post order → that's DFS, not BFS

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

Binary Tree Level Order Traversal II
Coming soon
Same BFS, then reverse the result list (or prepend each level) for bottom-up order.
Binary Tree Zigzag Level Order Traversal
BFS by level, but reverse every other level's sub-list (or use a deque per row).
Binary Tree Right Side View
BFS by level and keep only the last node of each level.
Average of Levels in Binary Tree
Same level loop, but sum each level and divide by its size.

Same pattern

←

Lowest Common Ancestor of a BST

Continue · Next problem

Binary Tree Right Side View