Binary Tree Level Order Traversal (LC 102)

Pattern: Tree BFS (Queue)
Difficulty: Medium
Key Concept: Process nodes level by level using a queue: dequeue a level’s worth of nodes, enqueue their children, repeat.

Problem Statement

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).

Input: root — may be null.
Output: List<List<Integer>> — outer list is levels, inner lists are values left-to-right.

Example

Output: [[3], [9, 20], [15, 7]].

1. Algorithm & Pseudocode

Brute force

DFS with depth index: traverse the tree; pass depth into recursion; append node.val to levels.get(depth). This is correct but interviewers often ask for the queue version first.
Two-pass: first compute height h, then for d = 0..h-1, scan entire tree collecting nodes at depth d — O(n × h).

Pseudocode (DFS brute — still O(n) time one visit)

result = list of empty lists

function dfs(node, depth):
    if node == null: return
    ensure result[depth] exists
    add node.val to result[depth]
    dfs(node.left, depth + 1)
    dfs(node.right, depth + 1)

dfs(root, 0)

Pseudocode (repeated depth scans — slower)

for d from 0 to height(root):
    row = collectNodesAtDepth(root, d)  // full tree walk each d
    add row to answer

Optimal (BFS)

If root is null, return empty list.
Queue q with root.
While q not empty:
- size = q.size() (nodes in current level).
- Loop size times: poll node, add value to current row, offer children.
- Add row to answer.

Pseudocode

q = [root]
answer = []
while q not empty:
    row = []
    sz = q.size()
    repeat sz times:
        n = q.pop_front()
        row.add(n.val)
        if n.left: q.add(n.left)
        if n.right: q.add(n.right)
    answer.add(row)
return answer

2. Step-by-Step Analysis (Beginner-Friendly)

Why queue: BFS explores in increasing distance from the root, which matches “level by level.”
Why snapshot q.size(): Before processing a level, the queue holds exactly that level’s nodes; children enqueued mid-loop belong to the next level.
DFS alternative is also O(n) and uses O(h) stack; BFS uses O(w) memory where w is max width (often worse for balanced trees).

3. The Dry Run

Tree

Iteration	Queue (front → back)	`sz`	Row collected
Start	`[3]`	1	—
Level 0	process `3` → enqueue `9`, `20`	1	`[3]`
After L0	`[9, 20]`	2	—
Level 1	process `9`; process `20` → enqueue `15`, `7`	2	`[9, 20]`
After L1	`[15, 7]`	2	—
Level 2	process `15`; process `7`	2	`[15, 7]`
Done	`[]`	—	—

ASCII levels

Level 0:  [ 3 ]

Level 1:  [ 9 , 20 ]

Level 2:  [ 15 , 7 ]

Tree sketch:

4. Java Solution

Brute Force

Repeated full-tree scan per depth (educational only).

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

class SolutionBrute {
    // Time: O(n * h), Space: O(n) for rows excluding recursion
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        int h = height(root);
        for (int d = 0; d < h; d++) {
            List<Integer> row = new ArrayList<>();
            collectAtDepth(root, d, 0, row);
            ans.add(row);
        }
        return ans;
    }

    private int height(TreeNode n) {
        if (n == null) return 0;
        return 1 + Math.max(height(n.left), height(n.right));
    }

    private void collectAtDepth(TreeNode n, int target, int cur, List<Integer> row) {
        if (n == null) return;
        if (cur == target) {
            row.add(n.val);
            return;
        }
        collectAtDepth(n.left, target, cur + 1, row);
        collectAtDepth(n.right, target, cur + 1, row);
    }
}

Optimal

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution {
    // Time: O(n), Space: O(w) queue width, worst O(n)
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        Deque<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            int sz = q.size();
            List<Integer> row = new ArrayList<>(sz);
            for (int i = 0; i < sz; i++) {
                TreeNode n = q.poll();
                row.add(n.val);
                if (n.left != null) q.add(n.left);
                if (n.right != null) q.add(n.right);
            }
            ans.add(row);
        }
        return ans;
    }
}

DFS optimal-by-time (same O(n), O(h) space)

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

    private void dfs(TreeNode n, int d, List<List<Integer>> ans) {
        if (n == null) return;
        if (ans.size() == d) ans.add(new ArrayList<>());
        ans.get(d).add(n.val);
        dfs(n.left, d + 1, ans);
        dfs(n.right, d + 1, ans);
    }
}

5. The “Java vs. Others” Edge

ArrayDeque is the standard Java queue; LinkedList as queue works but is usually slower.
Pre-size new ArrayList<>(sz) avoids internal resizing for each level.
For thread-safe level order you would use ConcurrentLinkedQueue — not needed on LeetCode.

6. Complexity Summary

Approach	Time	Space	Notes
Brute per-depth scan	O(n × h)	O(n) output	Retraverses tree for every depth
BFS queue	O(n)	O(w)	w = max breadth
DFS by depth index	O(n)	O(h) stack + O(n) output	Great when memory for queue is a concern