Introduction to Level Order Traversal Pattern

Level-order traversal visits a tree's nodes in waves radiating outward from the root: a FIFO queue holds exactly the nodes of the current wave, and by capturing the queue's length before draining it, each wave's children are enqueued without ever mixing into the current wave — this is BFS applied to a tree.

Recognize the pattern

• Problem asks to process/print/return nodes "level by level" or "row by row".
• Phrases like shortest path / minimum depth in an unweighted tree or graph, right-side view, zigzag traversal, connect next-right pointers, or average/max per level.
• You need to know how far a node is from the root, or need to stop as soon as some property is found on the shallowest matching level.

Brute force → optimal

Brute force: run a plain BFS that pushes children into one growing queue and prints nodes as they're dequeued, with no level boundary. To recover levels afterward you'd need a second pass — e.g. track each node's depth in a parallel array/map and bucket by depth, or insert a sentinel (null) marker after each batch of children. Both work but cost extra bookkeeping: a depth map costs O(n) extra space beyond the queue, and the sentinel approach requires special-casing the marker in the loop.

Optimal: before draining the queue for a level, snapshot levelSize = queue.size(). Because every node enqueued so far belongs to the current level, popping exactly levelSize times consumes precisely that level and no more — their children land after them in the queue, cleanly forming the next level. No sentinels, no separate depth tracking, O(n) time, O(width) auxiliary space.

Complexity, derived

Time: each of the n nodes is enqueued exactly once and dequeued exactly once (a node with no children still costs one dequeue). The inner for-loop's total iteration count across all levels equals the total number of dequeues, so total work is Σ(1 per node) = O(n). Emitting each value is O(1), so no term dominates.

Space: the queue never holds more nodes than the widest level of the tree, so auxiliary space is O(w) where w = max level width (worst case w ≈ n/2 for a complete binary tree's last level, so O(n)). The output structure (a list of levels) also stores all n values once, adding O(n) unavoidably.

Traced example

Tree: root 4; its children 5 (left) and 10 (right); 5's children are 3 (left) and 7 (right); 10 is a leaf. Node values are kept distinct on purpose so the queue snapshots below are unambiguous.

Result: [[4], [5, 10], [3, 7]] — flattened, [4, 5, 10, 3, 7].

Code

import java.util.*;

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

public class LevelOrder {
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // snapshot BEFORE draining
            List<Integer> level = new ArrayList<>(levelSize);
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }
}

Pitfalls

• Calling queue.size() inside the inner loop instead of snapshotting it before — since children get enqueued mid-loop, the size grows and the level never terminates correctly, merging levels together.
• Forgetting the null-root check, causing a NullPointerException on queue.offer(root) or the first poll.
• Enqueuing null children directly instead of checking != null first, corrupting the level-size count.
• Reusing DFS recursion with a manually threaded depth parameter when the problem needs level-boundary operations (level sums, rightmost node) — it works but is more error-prone than the queue's natural grouping.

When to use / when not — trade-offs

Use when the problem is naturally about layers: shortest path/minimum steps in an unweighted tree or graph, per-level aggregates, right-side view, zigzag order, connecting siblings, or serialization that must preserve row structure.

Avoid / reconsider when: edges are weighted (use Dijkstra/BFS-with-priority instead of plain queue BFS); the task is about root-to-leaf paths, subtree aggregates, or ancestor relationships — DFS is more natural there and needs only O(h) stack space versus BFS's O(w) queue space; for a very wide but shallow tree, BFS space can approach O(n) while DFS stays O(h), so DFS is the better memory trade-off in that shape.

Takeaways

• Snapshotting queue.size() before the inner loop is what turns generic BFS into level-order BFS — it is the entire trick.
• Time is O(n) because each node is enqueued and dequeued exactly once; space is O(w), the widest level, not O(n) in general.
• Choose BFS over DFS when the problem's unit of work is a level or a shortest hop count; choose DFS when it's a path or subtree.

Recall: Why must you capture queue.size() in a local variable before the inner for-loop, rather than checking queue.size() in the loop condition on every iteration?

Synthesized from standard BFS/level-order traversal treatments (CLRS graph-traversal foundations; common interview-prep pattern libraries) — worked example and complexity derivation original to this page.