102 · Binary Tree Level Order Traversal

Group every node by its depth. This is the pattern the rest of the tree-traversal set builds on — right side view, zigzag, max width and vertical order are all this same idea wearing a different hat.

1 — The problem

Given a binary tree, return a list of lists: one inner list per depth, each containing that level's values left to right. There are two structurally different ways to produce that grouping, and both are worth having cold, because later problems in this set specialise one or the other.

Neither is "more correct" — BFS makes the level boundary a first-class, inspectable event (useful whenever you need to compare siblings, like zigzag or width); DFS makes the depth a first-class parameter (useful whenever you need more than one coordinate per node, like vertical order's row and column). Both are visualised below, driven by the same example tree.

2 — Visualizing both approaches

2.1 BFS: the size-snapshot trick

The one line that makes this work is reading int sz = queue.size(); before the inner loop starts. The queue keeps growing as children get enqueued during that loop, so without the snapshot there's no way to know where one level ends and the next begins.

Queue<TreeNode> q = new LinkedList<>();q.add(root);while (!q.isEmpty()) {    int sz = q.size();    List<Integer> level = new ArrayList<>();    for (int i = 0; i < sz; i++) {        TreeNode nd = q.poll();        level.add(nd.val);        if (nd.left  != null) q.add(nd.left);        if (nd.right != null) q.add(nd.right);    }    result.add(level);}

2.2 DFS: depth as a parameter

The alternative carries a depth argument down the recursion instead of a queue. result grows lazily — the first node ever seen at a given depth is the one that creates that depth's inner list.

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

Same final grouping, arrived at from opposite directions: BFS discovers a level all at once and never needs to know its depth number; DFS discovers one node at a time and never needs a queue. Whichever a later problem in this set uses comes down to which extra piece of information it needs — a sibling to compare against (BFS) or a coordinate to compute (DFS).

3 — Complexity and edge cases

• Empty tree: return an empty list, not a list containing one empty list.
• Single node: one level, one element — the size-snapshot loop still works because it reads sz before touching the queue.
• Very wide levels: BFS's queue is the bottleneck; a level with 2^k nodes needs a queue of that size mid-traversal even though the whole tree might have few levels.
• Very deep, narrow trees: DFS's recursion depth becomes the bottleneck instead — convert to an explicit stack if stack-overflow on a skewed input is a real concern.

4 — Reference implementation

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < sz; i++) {
            TreeNode nd = q.poll();
            level.add(nd.val);
            if (nd.left  != null) q.add(nd.left);
            if (nd.right != null) q.add(nd.right);
        }
        result.add(level);
    }
    return result;
}