Binary Tree Level Order Traversal

“Level by level” is the definition of breadth-first search — a queue naturally processes nodes in that order. The only trick is snapshotting the queue’s size before draining each level, so nodes from the next level (enqueued mid-loop) do not get mixed into the current one.

BFS (queue, level by level)

OptimalTime O(n)Space O(n)

At the start of each iteration, len(queue) is exactly the number of nodes at the current level. Popping exactly that many, and appending their children, drains one full level per outer loop iteration.

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def levelOrder(self, root: TreeNode | None) -> list[list[int]]:
        if root is None:
            return []
        result = []
        queue = deque([root])
        while queue:
            level = []
            for _ in range(len(queue)):
                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

Tracing root = [3,9,20,null,null,15,7], watch the queue and the len(queue) snapshot: each outer loop drains exactly the number of nodes pushed for the current level, so children enqueued mid-drain wait for the next round.

len(queue) = 1⟶ drain exactly 1 (level 0)

Queue

← next to pop

Levels

1 / 8

currentseenresultcomparing

The queue starts as just the root. The outer loop reads `len(queue)` = 1 and freezes it as this level snapshot, then drains exactly 1 node into level 0.

Complexity: every node is enqueued and dequeued exactly once, doing O(1) work each time → O(n) time. The queue holds at most one full level, which can be up to ~n/2 nodes in a wide tree → O(n) space (the output array is also O(n), which does not change the bound).

DFS (recursive, tracking depth)

Time O(n)Space O(h)

BFS is not the only way: a pre-order DFS that carries its current depth can append directly into result[depth], creating a new sublist the first time a depth is reached.

class Solution:
    def levelOrder(self, root: TreeNode | None) -> list[list[int]]:
        result = []

        def dfs(node: TreeNode | None, 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

Why consider this: still O(n) time, and it trades the queue’s O(n) width for the recursion stack’s O(h) depth — a win for a wide, shallow tree, though worse than BFS for a deep, narrow one. It also visits nodes in a different order (root before its children, not strictly level by level in real time), which only matters if intermediate order is observed.

Binary Tree Level Order Traversal

BFS (queue, level by level)

DFS (recursive, tracking depth)

More Trees practice