Binary Tree Level Order Traversal

Interview Prep

StandardTreestreesbfs

The problem

Return the values of a binary tree, grouped by level (root level is index 0). Output a list of lists. 

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

Pattern: BFS with level snapshot

Standard BFS on a tree, with one critical detail: capture len(q) before the inner loop starts. That count is exactly the number of nodes at the current level; after processing them you'll have grown the queue by their children, which belong to the next level. Without that snapshot you can't tell where one level ends and the next begins.

Solution: BFS

from collections import deque

def level_order(root: Node | None) -> list[list[int]]:
    if root is None: return []
    q, out = deque([root]), []
    while q:
        level = []
        for _ in range(len(q)):            # snapshot the level size FIRST
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out

Trace

Tree:        3
            / \
           9  20
              / \
             15  7

Level 0: q=[3].          level=[3].        push 9, 20.   q=[9,20].
Level 1: q=[9, 20].      level=[9, 20].    push 15, 7.   q=[15,7].
Level 2: q=[15, 7].      level=[15, 7].    no children.  q=[].
End.

return [[3], [9, 20], [15, 7]]

Alternative: DFS with a depth argument

Same answer, different traversal order. DFS visits the leftmost branch all the way down first, but because we track depth explicitly and append to out[depth], the output is still grouped by level. Slightly less natural for this problem but a useful template — many "answer per level" or "tag with depth" problems reduce to this DFS form. 

def level_order_dfs(root):
    """Same answer via DFS with explicit depth."""
    out = []
    def walk(node, depth):
        if node is None: return
        if depth == len(out): out.append([])
        out[depth].append(node.val)
        walk(node.left,  depth + 1)
        walk(node.right, depth + 1)
    walk(root, 0)
    return out

Complexity

Variations worth knowing