Binary Tree Level Order Traversal

1. Problem & Core Objective

Return the node values level by level, left to right, as a list of lists.

      3
     / \          →  [[3], [9,20], [15,7]]
    9  20
       / \
      15  7

Constraints: 0 <= nodes <= 2000 · -1000 <= Node.val <= 1000

What's actually being tested: BFS with a queue, and specifically the one line that separates the levels — snapshotting q.size() before processing. Every DFS solution so far has been depth-first; this is the section's pivot to breadth-first, and questions 9 and 10 reuse it directly.

2. First-Principles Thought Process

Why DFS is the wrong shape here

Depth-first goes all the way down one branch before touching the next. The output needs nodes grouped by distance from the root, and DFS visits them in an order that jumps between levels constantly.

You can make DFS work by passing the depth down and appending into result[depth] — that's approach 2 — but it's working against the traversal order rather than with it.

BFS visits in exactly the right order

A queue processes nodes in the order they were discovered. Start with the root; each time you dequeue a node, enqueue its children. Children are always discovered after everything at their parent's level, so the queue naturally holds nodes in non-decreasing order of depth.

The problem: where does one level end?

BFS gives the right order but not the grouping. Dequeue nodes one at a time and you get 3, 9, 20, 15, 7 — correct sequence, no level boundaries.

The fix: snapshot the size

At the moment a level begins, the queue contains exactly that level's nodes. So capture the size first, then process precisely that many:

int size = q.size();                      // exactly this level's nodes
for (int i = 0; i < size; i++) { ... }    // children enqueued here belong to the NEXT level

Without the snapshot, q.size() grows during the loop as children are added, and the loop drains everything — merging all levels into one.

That single line is the whole technique, and it recurs in questions 9, 10, and in the graph section.

3. Solution Paths

Approach 1 — BFS with a level snapshot (optimal)

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> q = new ArrayDeque<>();
    q.offer(root);

    while (!q.isEmpty()) {
        int size = q.size();                       // snapshot BEFORE enqueuing children
        List<Integer> level = new ArrayList<>(size);

        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left  != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

Trace — [3,9,20,null,null,15,7]:

• Time O(n) · Space O(w) — the widest level, up to n/2

Counter-questions on this approach

⭐ "What breaks without the int size snapshot?"

The levels merge into one. Inside the loop I enqueue children, so q.size() keeps growing — a while (!q.isEmpty()) inner loop would drain the entire tree and produce [[3,9,20,15,7]].

Capturing the size first freezes how many nodes belong to the current level. Anything enqueued during the loop is beyond that count and is therefore handled in the next round, which is exactly the next level.

⭐ "Why is the space O(w) and not O(n)?"

The queue only ever holds one level plus the children being added, so it's bounded by the maximum width. For a perfect tree the last level has n/2 nodes, so O(w) is O(n) there — but for a degenerate tree it's O(1), where DFS would be O(n) stack.

Note the output itself is O(n); O(w) is the auxiliary space.

"Why ArrayDeque rather than LinkedList?"

Faster and lower memory — LinkedList allocates a node object per element. ArrayDeque forbids null elements, which is fine since I guard both offer calls. See 02.

"Why check node.left != null before offering?"

Two reasons. ArrayDeque throws NullPointerException on a null element. And even with a null-tolerant queue, enqueuing nulls would put phantom entries in the size count and corrupt the level boundaries.

"Could you pre-size the inner list?"

Yes — new ArrayList<>(size) avoids the internal array growing and recopying. A small constant-factor win, and free since the size is already known.

Approach 2 — DFS carrying the depth

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(root, 0, result);
    return result;
}

private void dfs(TreeNode node, int depth, List<List<Integer>> result) {
    if (node == null) return;
    if (depth == result.size()) result.add(new ArrayList<>());   // first node at this depth
    result.get(depth).add(node.val);
    dfs(node.left,  depth + 1, result);
    dfs(node.right, depth + 1, result);
}

• Time O(n) · Space O(h) stack

Counter-questions on this approach

⭐ "DFS visits out of level order. Why is the output still correct?"

Because the depth indexes the output rather than the visit order determining it. Each node appends into result[depth], so grouping is by depth regardless of when the node is visited.

Left-to-right ordering within a level is preserved because I recurse left before right, and preorder guarantees every node in the left subtree is visited before any node in the right subtree — so they're appended in the correct relative order.

⭐ "What is if (depth == result.size()) doing?"

Creating the list for a level the first time it's reached. Because DFS descends leftmost-first, the first node seen at depth d arrives when result has exactly d lists, so depth == result.size() is precisely the "new level" condition.

It works only because depths are reached in increasing order with no gaps — you can never reach depth d+1 before depth d. Worth stating, because it's an invariant rather than a coincidence.

"Which would you submit?"

BFS. The problem is stated in terms of levels, and BFS expresses that directly — the code reads the way the requirement is worded. DFS is a clever equivalent, and it's genuinely better when the tree is wide and shallow, since O(h) beats O(w) there.

"Is result.get(depth).add(...) efficient?"

ArrayList.get is O(1) and amortized add is O(1), so yes. If result were a LinkedList the get(depth) would be O(depth) and the whole thing would degrade to O(n·h).

Comparison

4. Why the Optimal Wins

Both are O(n) and both are correct — the choice is expressive fit and which space bound suits the tree.

BFS wins on fit: the problem asks for levels, and BFS processes levels. The snapshot line makes the grouping explicit rather than implicit in an index. And because questions 9 and 10 need per-level reasoning too, the BFS skeleton is worth having automatic.

The framing worth keeping:

BFS gives you the right order; int size = q.size() gives you the grouping. Snapshot before you enqueue, and each round of the loop is exactly one level.

5. Java Prerequisites

The level-order skeleton — memorize this:

Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
    int size = q.size();                         // the whole trick
    for (int i = 0; i < size; i++) {
        TreeNode n = q.poll();
        // ... use n ...
        if (n.left  != null) q.offer(n.left);
        if (n.right != null) q.offer(n.right);
    }
    // one level complete
}

Queue methods — prefer the non-throwing pair:

q.offer(x);   // returns false if full, rather than throwing
q.poll();     // returns null if empty, rather than throwing
q.add(x); q.remove();   // the throwing equivalents

ArrayDeque forbids nulls; LinkedList allows them but is slower.

Return new ArrayList<>() for a null root, not null — callers expect an empty list.

6. Interview Communication Guide

Clarifying questions: Should each level be its own list (yes)? Left to right, or alternating (left to right; alternating is the zigzag follow-up)? What should a null root return (an empty list)? How wide could the tree be (it decides BFS vs DFS on space)?

The pitch

"The output is grouped by distance from the root, so BFS is the natural fit — a queue visits nodes in exactly that order.

The one subtlety is where a level ends. BFS gives the right sequence but no boundaries: dequeue one at a time and you get 3, 9, 20, 15, 7 with no grouping.

The fix is to snapshot the queue size at the top of each round. At that moment the queue holds exactly the current level's nodes, so I process precisely that many. Children enqueued during the loop are beyond the snapshot, so they're handled in the next round — which is the next level.

That line is load-bearing: without it, q.size() grows as I enqueue and the loop drains the whole tree into a single level.

O(n) time, O(w) auxiliary space where w is the widest level.

There's a DFS alternative that carries the depth and appends into result[depth]. It's O(h) instead of O(w), so it's better on wide shallow trees — but BFS reads the way the problem is worded, and the same skeleton is what the right-side-view and zigzag variants need."

Edge cases to volunteer:

Name the degenerate chain. It's where O(w) is O(1) and DFS would be O(n) — the clearest illustration that the two approaches trade rather than dominate.

7. Follow-Up Questions — Modified Constraints

⭐ "Zigzag level order — alternate left-to-right and right-to-left."

LeetCode 103. Keep the same BFS and reverse alternate levels — or better, build each level into a Deque and addFirst instead of addLast on odd levels, which avoids the reversal pass. Don't try to alternate the traversal direction; that breaks the parent-child ordering and is a common wrong turn.

⭐ "Return the right side view — the last node of each level."

Question 9. Same BFS; take the element at index size - 1 in each round. One line different, which is a nice illustration that the level-order skeleton is the reusable part.

"Return the levels bottom-up."

LeetCode 107. Build normally and reverse at the end, or insert each level at index 0 — though the latter is O(n) per insert into an ArrayList, making it O(n·h). Use LinkedList.addFirst or reverse once at the end.

"Compute the average value of each level."

LeetCode 637. Sum within the level loop and divide by size. Use a long or double accumulator — 2000 nodes at 1000 each is only 2 × 10^6 so int is safe here, but the habit matters when the bounds grow.

"Find the largest value in each level."

Same skeleton, tracking a max instead of a list. This family — average, max, sum, count, first, last — is all the same loop with a different accumulator, which is worth saying explicitly.

"What if the tree were extremely wide — 10^6 nodes on one level?"

BFS holds all of them at once, so O(w) becomes 10^6 queue entries. DFS with a depth index would be O(h) in auxiliary space, though the output is still O(n). If even the output is too large, you'd stream each level to the consumer as it completes rather than accumulating.

"Do it for an n-ary tree."

Identical, except you enqueue every child rather than two: for (Node c : node.children) q.offer(c);. The level snapshot is unchanged — which is a good sign it captured the idea rather than the binary special case.