Free lesson · DSA Mastery - Interview Prep, End to End

Binary Tree Level Order Traversal

Medium7 min readdsabinary-tree

Binary Tree Level Order Traversal

Binary Tree Level Order Traversal is the foundational output of the level-sweep pattern: return the node values grouped by level as a list of lists. It's the same breadth-first sweep as the previous two topics, but now the per-level reduction is "collect the values into a sublist" rather than "count the level" or "average it." That makes this the literal template that Average of Levels specialized - and everything else in this sub-group is a variation on the list-of-lists this problem produces. We present the iterative BFS (the canonical answer) and a DFS that buckets values by depth.

The insight: a breadth-first sweep naturally visits nodes one level at a time. If you snapshot the queue size at the start of each level, the next batch of dequeued nodes is exactly that level - collect their values into a sublist, enqueue their children, and repeat. The result is the levels in top-to-bottom order, each a left-to-right list.

The Problem

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

Example 1:

Input:  root = [3,9,20,null,null,15,7]
Output: [[3], [9,20], [15,7]]

Example 2:

Input:  root = [1]
Output: [[1]]

Example 3:

Input:  root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

Approaches Overview

#	Approach	Time	Space	Verdict
1	Iterative BFS level sweep	O(n)	O(w)	Canonical
2	DFS bucketing by depth	O(n)	O(h + n)	Works, depth-indexed

Both are O(n). BFS sweeps level by level, collecting each level's values into a sublist - the direct, expected solution. DFS recurses while appending each node's value to the sublist for its depth, which also produces correctly-ordered levels. BFS is the idiomatic choice for an explicitly level-based output.

Approach 1: Iterative BFS Level Sweep - Canonical

The Idea

Initialize a queue with the root (if non-null). For each level, snapshot the queue size, create a fresh sublist, then dequeue exactly that many nodes - appending each value to the sublist and enqueuing its children. Add the completed sublist to the result and continue until the queue empties.

Logic Flowchart

graph TD
    A["if root null: return []; queue = [root]; result = []"] --> B{"queue not empty?"}
    B -->|No| C["return result"]
    B -->|Yes| D["size = queue.size(); level = []"]
    D --> E["dequeue 'size' nodes: level.add(val); enqueue children"]
    E --> F["result.add(level)"]
    F --> B

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the BFS level sweep. For each level we snapshot the queue size, collect exactly that many dequeued node values into a fresh sublist while enqueuing their children, then append the sublist to the result.

Code

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 size = queue.size();              // nodes on this level
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; 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);                    // one sublist per level
    }
    return result;
}

// Usage:
// levelOrder([3,9,20,null,null,15,7]) -> [[3],[9,20],[15,7]]

This Java code sweeps level by level with a queue. For each level it collects all node values into a sublist while enqueuing their children, then adds the sublist to the result list.

Step-by-Step Walkthrough

A frame-by-frame trace on root = [3,9,20,null,null,15,7]:

graph LR
    F0["queue=[3] size1 level=[3]; enqueue 9,20"]
    F1["queue=[9,20] size2 level=[9,20]; enqueue 15,7"]
    F2["queue=[15,7] size2 level=[15,7]; no children"]
    F3["result = [[3],[9,20],[15,7]]"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough groups nodes by level. Level zero collects three, level one collects nine and twenty, level two collects fifteen and seven, producing the list of lists.

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

Complexity

Time: O(n). Space: O(w) for the queue (plus O(n) for the output).

Approach 2: DFS Bucketing by Depth

The Idea

Recurse with the current depth. The result is a list of sublists indexed by depth; when the recursion first reaches a new depth, append a fresh empty sublist. Add each node's value to result[depth], then recurse left and right with depth + 1. Because preorder visits a node before its children and left before right, each sublist fills in correct left-to-right order.

Logic Flowchart

graph TD
    A["dfs(node, depth)"] --> B{"node == null?"}
    B -->|Yes| C["return"]
    B -->|No| D{"depth == result.size()?"}
    D -->|Yes| E["result.add(new sublist)"]
    D -->|No| F["(sublist exists)"]
    E --> G["result[depth].add(val)"]
    F --> G
    G --> H["dfs(left, depth+1); dfs(right, depth+1)"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This flowchart shows DFS bucketing by depth. When recursion first reaches a depth it adds a new sublist; each node appends its value to its depth's sublist, then recurses left and right with depth increased by one.

Code

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

private static 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);                            // left before right
    dfs(node.right, depth + 1, result);
}

This Java code recurses with the current depth. It creates a new sublist the first time a depth is reached, appends each node's value to its depth's sublist, and recurses left then right so values fill in left-to-right order.

Complexity

Time: O(n). Space: O(h) recursion stack (plus O(n) output).

Complexity Comparison

Approach	Time	Space	Key Idea	When to Use
BFS level sweep	O(n)	O(w)	Collect each level batch	Canonical
DFS bucketing	O(n)	O(h)	Append to depth-indexed sublist	When DFS is preferred

Both produce identical correctly-ordered output. BFS is the natural, expected answer for a level-order question and makes the level boundaries explicit. DFS is a clever alternative - preorder left-to-right keeps each depth's sublist correctly ordered - and is handy when you're already traversing depth-first for other reasons.

Variations & Follow-ups

How does Average of Levels relate to this problem?

Average of Levels is this exact sweep with a different per-level reduction: instead of result.add(level) it appends the level's average. The previous topic was a specialization; this one is the general template that emits the raw groupings. Once you can produce the list-of-lists, any per-level transformation (sum, max, average, count) is a trivial substitution in the same loop.

Why does DFS preserve left-to-right order within each level?

Preorder recursion visits the left child before the right at every node, and it visits a parent before either child. So within any fixed depth, nodes are appended in the same left-to-right order they'd appear in a level sweep. The depth index routes each value to the correct sublist, and the visit order keeps each sublist internally ordered. This is why depth-bucketing DFS matches BFS output exactly.

How would you produce bottom-up level order?

For bottom-up order (deepest level first), build the list-of-lists normally, then reverse it - or insert each new level at the front of the result. The traversal is unchanged; only the final assembly differs. This is a common variant ("Level Order Traversal II") and a one-line change to either approach.

When is BFS's space better or worse than DFS's?

BFS uses O(w) queue space (max level width); DFS uses O(h) stack space (height). For a wide, balanced tree, the bottom level holds ~n/2 nodes, so BFS's queue is large while DFS's stack is only O(log n). For a skewed chain, DFS recurses O(n) deep while BFS's queue stays tiny. The tree's shape decides which is more economical - though both are O(n) including the unavoidable output.

What about edge cases?

Empty tree (Example 3): Return an empty list immediately.
Single node (Example 2): One sublist with one value.
Skewed chain: Each level is a singleton sublist.
Perfect tree: Level sizes double each level (1, 2, 4, …).

Common Interview Pitfalls

Forgetting the empty-tree guard. Without root == null, BFS enqueues a null and crashes.
Not snapshotting queue.size(). Reading it inside the loop merges adjacent levels.
Reusing one sublist across levels. Create a fresh level list each iteration.
DFS missing the new-depth check. You must add a sublist the first time each depth is reached, or indexing fails.

Why This Topic Matters

Binary Tree Level Order Traversal is the archetype of the entire sub-group: every other level-order problem (right-side view, zigzag, width, vertical order, completeness) is this list-of-lists with a twist on what you collect or how you order it. Mastering both the BFS sweep and the depth-bucketing DFS gives you two interchangeable engines for any level-structured question, and it makes the per-level-reduction idea concrete.

The next topic, Binary Tree Right Side View, asks what you'd see standing to the right of the tree: the rightmost node on each level, top to bottom. It's the level sweep keeping only the last node of each level - a one-line tweak to the template (take the final dequeued node per level) - and a clean illustration that many "view" and "selection" problems are just level order with a per-level pick.

Back to DSA Mastery - Interview Prep, End to End