Binary Tree Level Order Traversal

Problem

Given the root of a binary tree, return its level order traversal: a list of lists, where the first inner list holds the values at depth 0 (the root), the second holds depth 1 left-to-right, and so on down the tree.

Examples

Example 1

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

Depth 0 is just the root 3; depth 1 is 9 then 20; depth 2 is 20’s children 15 then 7.

Example 2

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

A single node is one level.

Example 3

Input: root = []
Output: []

An empty tree has no levels.

Constraints

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

Expected: visit every node once — O(n) time — while grouping output by depth.

Think about it first

TL;DR

BFS with a level-size snapshot — O(n) time, O(n) space; depth-tagged DFS is the classic alternative.

Approach 1 — Brute force: one pass per level

The naive idea: first compute the tree’s height, then for each depth d run a separate traversal that collects only the nodes exactly d edges below the root.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional, List


def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    def height(node: Optional[TreeNode]) -> int:
        if node is None:
            return 0
        return 1 + max(height(node.left), height(node.right))

    def collect(node: Optional[TreeNode], depth: int, out: List[int]) -> None:
        if node is None:
            return
        if depth == 0:
            out.append(node.val)
            return
        collect(node.left, depth - 1, out)
        collect(node.right, depth - 1, out)

    result: List[List[int]] = []
    for d in range(height(root)):
        level: List[int] = []
        collect(root, d, level)
        result.append(level)
    return result

Complexity: O(n·h) time — collecting level d re-walks all d levels above it, so a degenerate 2000-node chain does ~2·10^6 node visits. O(h) extra space. It passes here, but the repeated re-walking is exactly what a queue eliminates.

Approach 2 — BFS with level-size snapshots

Breadth-first search (BFS), driven by a FIFO queue, already visits nodes level by level; the missing piece is where levels end. When a level begins, the queue holds exactly that level and nothing else, so len(queue) is the level’s size. Pop that many nodes, and everything enqueued meanwhile is the next level.

For Example 1, the tree and its levels are:

graph TD
    3 --- 9
    3 --- 20
    20 --- 15
    20 --- 7

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque
from typing import Optional, List


def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    if root is None:
        return []
    result: List[List[int]] = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        level: List[int] = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

Walkthrough on Example 1 (root = [3,9,20,null,null,15,7]):

1. Queue = [3], size 1 → pop 3, emit [3], enqueue 9, 20.
2. Queue = [9, 20], size 2 → pop 9 (no children), pop 20 (enqueue 15, 7), emit [9, 20].
3. Queue = [15, 7], size 2 → pop both leaves, emit [15, 7].
4. Queue empty → return [[3],[9,20],[15,7]].

Complexity: O(n) time — each node enqueued and dequeued once. O(n) space: the queue holds up to the widest level (which can be ~n/2 nodes), plus the output.

Approach 3 — DFS carrying the depth

BFS is not mandatory. A depth-first search that tracks its current depth can drop each value into result[depth]. Because DFS visits any level’s nodes left-to-right (preorder: node before children, left before right), each inner list still comes out in the correct order. The same approach generalizes to any problem keyed by depth.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional, List


def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    result: List[List[int]] = []

    def dfs(node: Optional[TreeNode], depth: int) -> None:
        if node is None:
            return
        if depth == len(result):
            result.append([])
        result[depth].append(node.val)
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)

    dfs(root, 0)
    return result

Walkthrough on Example 1: visit 3 at depth 0 → [[3]]; visit 9 at depth 1 → [[3],[9]]; visit 20 at depth 1 → [[3],[9,20]]; visit 15 then 7 at depth 2 → [[3],[9,20],[15,7]]. Same answer, no queue.

Complexity: O(n) time, O(h) auxiliary space for the recursion (better than BFS’s O(width) on wide bushy trees; worse on skewed ones).

Common pitfalls

• Reading len(queue) inside the loop: the size must be snapshotted before popping starts — the queue grows with children as you go, and a live read merges levels.
• Enqueueing None children: either guard before enqueueing (as above) or guard after popping — doing neither crashes; doing both is harmless but noisy.
• Empty-tree crash: root = None must return [] before any queue is built.
• In the DFS variant, indexing before extending: result[depth] throws IndexError the first time a depth is reached unless you append a fresh list exactly when depth == len(result).

Pattern takeaway

The level-size snapshot solves every “by level” tree problem: read len(queue) at the top of the round, and the queue partitions into current level and next level. Right-side view, zigzag traversal, level averages, and “largest value per row” are the same loop with a different line inside. Keep the depth-tagged DFS available too; some problems, such as those combining depth with path state, are more natural recursively.