Level Order Traversal

Signal

"Group by level" or "shortest steps away" is the BFS trigger — process nodes queue-first rather than recursively depth-first, and freeze the queue's current length at the start of each round to know exactly where one level ends and the next begins.

Approach

Standard BFS with a queue seeded with the root. At each iteration, snapshot the current queue length as level_size, pop exactly that many nodes, collect their values, and push their children — those pushes belong to the next level, so the snapshot is what keeps levels from bleeding together.

Skeleton

queue = [root] if root else []
result = []
while queue:
    level_size = len(queue)
    level = []
    for _ in range(level_size):
        node = queue.pop(0)
        level.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    result.append(level)

Solution

from collections import deque


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


def level_order(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

Complexity

O(n) time — each node enqueued and dequeued once. O(n) space: the queue holds up to one full level (which can be O(n) for a wide tree), plus the output.

Pitfalls

• A plain list with .pop(0) is O(n) per call — use collections.deque for O(1) popleft, or the whole traversal silently degrades to O(n²).
• Snapshotting len(queue) before the inner loop is what separates levels; reading the queue's length inside a naive loop without freezing it merges levels together.