Difficulty: MediumTrees

Binary Tree Level Order Traversal

Problem in Plain English

Given the root of a binary tree, return its node values grouped level by level, from the root down to the deepest leaves, left to right within each level.

Problem Statement

Given the root of a binary tree, return the level order traversal of its node values.

Visit all nodes at each depth from left to right before moving to the next depth, grouping the values of each level into its own list.

Constraints

The number of nodes is between 0 and 2000, inclusive.
Each node value is between -1000 and 1000, inclusive.

Examples

Example 1

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

Root 3 is at depth 0. Its children 9 and 20 are at depth 1, in that order. Only 20 has children, so depth 2 contains 15 followed by 7; missing children contribute no placeholders.

Example 2

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

Root 1 is the only node, so its value forms one inner list. The result must be [[1]], rather than a flat [1].

Example 3

Input: root = []
Output: []

There are no nodes or depths to report. Return an empty outer list, not a list containing an empty level.

Example 4

Input: root = [1,2,3,null,4,5,null]
Output: [[1],[2,3],[4,5]]

Node 4 is the right child of 2 and node 5 is the left child of 3. Their parents occur left to right as 2 then 3, so 4 must precede 5 despite the different child sides.

Intuition

Depth is the number of edges from the root. Grouping by depth turns Example 1 into root level [3], its child level [9,20], then [15,7]. A depth-first traversal can store each value in the bucket for its depth. A queue can instead finish the current frontier, the nodes waiting at one depth, before starting the next. In either case, visiting left children before right children preserves the required horizontal order.

Approaches

Recursive Depth Buckets

Solution Details

Reveal Recursive Depth Buckets: intuition, complexity, and code

Intuition

Carrying the depth down a depth-first walk tells each node exactly which result bucket it belongs to, so levels assemble themselves without a queue. Opening a new bucket the first time a depth appears keeps left-to-right order for free via the call sequence.

Step-by-Step Logic

Start dfs(3, 0): result is empty, so open level 0 and store 3, giving [[3]].
Descend to dfs(9, 1): open level 1 and store 9, giving [[3], [9]].
Both children of 9 are null and return at once.
Back at depth 1, visit dfs(20, 1) and append 20 to the open level: [[3], [9, 20]].
Visit dfs(15, 2) and dfs(7, 2): open level 2 and store both, giving [[3], [9, 20], [15, 7]].

Why It Works

Each recursive call receives the exact depth: the root starts at 0 and each child adds 1. Thus each value is appended to exactly its required bucket. The first encounter with a depth creates its bucket, and no depth can be skipped because reaching it requires passing through its parent. For any two nodes at the same depth, their paths first diverge at a common ancestor: the left subtree is completely traversed before the right subtree, so their append order is left to right. Every node is visited once and the original tree is only read.

Dry Run

Recursive Depth Buckets: variable states at each step
Call or return	Depth	Bucket action	Result after event
enter dfs(3)	0	create bucket 0; append 3	[[3]]
enter dfs(9)	1	create bucket 1; append 9	[[3],[9]]
dfs(9.left=null), then dfs(9.right=null); return from 9	2	both null calls return without appending	[[3],[9]]
enter dfs(20)	1	reuse bucket 1; append 20	[[3],[9,20]]
enter dfs(15)	2	create bucket 2; append 15	[[3],[9,20],[15]]
dfs(15.left=null), then dfs(15.right=null); return from 15	3	no change	[[3],[9,20],[15]]
enter dfs(7)	2	reuse bucket 2; append 7	[[3],[9,20],[15,7]]
dfs(7.left=null), then dfs(7.right=null); return from 7	3	no change	[[3],[9,20],[15,7]]
return from 20, then 3; outer call returns	1, then 0	all calls complete	[[3],[9,20],[15,7]]

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

For n nodes and height h, every node makes one append, taking O(n) time. Excluding the returned lists, auxiliary recursion storage is O(h), worst-case O(n). The result itself stores n values plus h distinct inner lists, also O(n); total extra allocation remains O(n). All lists are local to each call. A depth-2000 chain can exceed stack defaults: verification uses Java -Xss16m, Node --stack_size=16384 and the published Python entry wrapper temporarily reserves recursion limit 12000 and restores it afterward.

Code

Solution.java

1import java.util.ArrayList;2import java.util.List;3
4class TreeNode {5    int val;6    TreeNode left, right;7    TreeNode(int val) { this.val = val; }8}9
10class Solution {11    public List<List<Integer>> levelOrder(TreeNode root) {12        List<List<Integer>> result = new ArrayList<>();13        dfs(root, 0, result);14        return result;15    }16
17    private void dfs(TreeNode node, int depth, List<List<Integer>> result) {18        if (node == null) return;19        // The first visit to a depth creates its own independent output bucket.20        if (result.size() == depth) {21            result.add(new ArrayList<>());22        }23        result.get(depth).add(node.val);24        // Left-first DFS preserves horizontal order within each depth bucket.25        dfs(node.left, depth + 1, result);26        dfs(node.right, depth + 1, result);27    }28}

Hints

Hint 1

A queue releases nodes in discovery order, which is exactly level order.

Hint 2

Read the queue length before draining a level so newly enqueued children do not join the current batch.

Hint 3

Alternatively, pass the depth down a recursive walk and append each value to the bucket for its depth.

Edge Cases

An empty root returns an empty list before any queue is created.
A skewed chain produces one singleton list per depth; recursion depth equals the node count.
Missing children are skipped without null placeholders, including the gaps in Example 4.
Duplicate and negative values still occupy separate output positions; do not deduplicate.
A broad tree uses a wide queue; a deep tree stresses recursion. Both must preserve every original node and child reference.

Common Mistakes and Interview Tips

Looping against the live queue length instead of a snapshot, which mixes two levels into one batch.
Using Python list pop(0) or JavaScript shift() repeatedly on broad frontiers can introduce quadratic copying; use deque or an index with level-boundary compaction.
Visiting right children before left children reverses required horizontal order, even though depth grouping remains correct.
Reusing the same inner list for several levels aliases mutable output. Allocate a fresh list for every level and keep results local to each invocation.
Confusing auxiliary space with returned output: recursion uses O(height), BFS uses O(width), and both allocate O(n) output.
Assuming default recursion stacks handle a 2000-node chain. Configure and restore Python recursion limits outside the helper, or choose the iterative queue approach.

Key Takeaway

Level-by-level work means breadth-first search with a size snapshot; the snapshot is what separates one level from the next.