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


class Solution:
    def levelOrder(self, 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

The insight: breadth-first search (BFS) — the traversal driven by a FIFO queue — already visits nodes level by level; the only missing piece is where levels end. At the moment a level begins, the queue contains exactly that level and nothing else, so len(queue) is the level’s size: pop exactly that many, and everything you enqueued meanwhile is exactly the next level.

# 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


class Solution:
    def levelOrder(self, 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

The insight: BFS isn’t mandatory — a depth-first search that knows 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. This is the standard trick when a “level” question meets a recursive mood, and it generalizes to problems 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


class Solution:
    def levelOrder(self, 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 is the master key for every “by level” tree problem: freeze len(queue) at the top of the round, and the queue cleanly partitions into current level / next level. Right-side view, zigzag traversal, level averages, and “largest value per row” are all this loop with a different line inside. Keep the depth-tagged DFS in reserve — some problems (e.g. combining depth with path state) are more natural recursively.