Binary Tree Level Order Traversal

Return tree values one level at a time.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Binary Tree Level Order Traversal: Snapshotting the queue length separates the current tree level from children appended for the next level.

Input and goalReturn tree values one level at a time.

Queue the rootFor tree [3,9,20,null,null,15,7], initialize answer = [] and queue = [3]. The drawn edges show 3 -> 9, 3 -> 20, 20 -> 15, and 20 -> 7.

• 3queued
  • 9
  • 20
    • 15
    • 7

queueState[3]answer[]

Recognize it

Use this BFS form when a tree answer is grouped by depth, processed left-to-right by level, or must compute one aggregate per level rather than one flat visitation order.

Keep true

At each while-loop start, the queue contains exactly one complete next level in left-to-right order. Iterating the captured length consumes only that level while appending its children for the following level.

Reuse it

Capture the frontier size before expanding it whenever output or timing is grouped by BFS depth; this transfers to right-side view, level averages, shortest unweighted paths, and wave simulations.

Pattern: BFS.

Simple idea: The queue contains the next level. Read its current size before adding any children. That size tells you how many nodes belong to this level.

from __future__ import annotations
from collections import deque
from dataclasses import dataclass

@dataclass(eq=False, slots=True)
class TreeNode:
   val: int
   left: TreeNode | None = None
   right: TreeNode | None = None

def level_order(root: TreeNode | None) -> list[list[int]]:
   if root is None:
      return []

   answer: list[list[int]] = []
   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)
      answer.append(level)
   return answer

Cost: $O(n)$ time and $O(w)$ space, where $w$ is the widest level.