Binary Tree Level Order Traversal

Most tree problems are depth-first. This one is the template for the other family: problems that talk about levels — "each row", "the rightmost node you can see", "the shallowest leaf", "the average of each level". All of them are this lesson's code with one or two lines changed, so it is worth knowing cold.

The one idea to take away is a single line: reading the queue's length before processing a level. Without it, nodes from two levels mix together in the queue and there is no way to tell them apart.

The problem

Given the root of a binary tree, return its values level by level: a list of lists, where the first list holds the root, the second holds the root's children from left to right, and so on.

        1      /   \     2     3    / \     \   4   5     6      /     7

• For this tree → [[1], [2, 3], [4, 5, 6], [7]].
• For an empty tree → [].

Constraints: 0 ≤ n ≤ 10⁵ nodes, not necessarily balanced.

Clarifying questions

• Left to right within each level? Yes.
• Empty tree? Return an empty list, not [[]].
• Values or nodes? Values.
• Any limit on depth? A chain of 10⁵ nodes is allowed, which matters for recursive solutions.

Approach 1: the simple way — one pass per level

For each depth d from 0 to the height, walk the tree and collect every node at depth d.

1def level_order_brute(root: Optional[TreeNode]) -> list[list[int]]:2    """For each depth d, walk the whole tree and collect nodes at depth d."""3    def collect(node: Optional[TreeNode], d: int, out: list[int]) -> None:4        if node is None:5            return6        if d == 0:7            out.append(node.val)8            return9        collect(node.left, d - 1, out)10        collect(node.right, d - 1, out)1112    result = []13    for d in range(max_depth(root)):14        level: list[int] = []15        collect(root, d, level)16        result.append(level)17    return result

max_depth is the function from the core idea lesson. Visiting the left child before the right keeps each level in left-to-right order.

The cost: collecting level d revisits every node above level d again. On a balanced tree the levels double in size, so the repeats add up to about 2n — fine. On a chain of n nodes, level d costs d + 1 visits, and the total is about n²/2. At 10⁵ nodes that is 5 × 10⁹ visits, and each pass also recurses up to 10⁵ deep. Too slow and too deep.

The key insight

A queue visits nodes in the order they were discovered. If you start with the root and, every time you remove a node, add its children to the back, then all of level 1 is discovered before any of level 2, all of level 2 before any of level 3, and so on. The queue never goes back up.

That gives the right order, but a single queue does not mark where one level ends. The trick: at the start of each round, the queue holds exactly one full level and nothing else. So read len(queue) then, and pop exactly that many nodes. The children you push during those pops are the next level, and they wait behind the snapshot.

The invariant to say out loud: at the top of the loop, the queue holds all of the next level and only that level.

Approach 2: BFS with a level-size snapshot

1from collections import deque234def level_order(root: Optional[TreeNode]) -> list[list[int]]:5    """Values of the tree, one list per level, left to right."""6    if root is None:7        return []8    result = []9    queue = deque([root])10    while queue:11        level_size = len(queue)           # snapshot: this many nodes are on this level12        level = []13        for _ in range(level_size):14            node = queue.popleft()15            level.append(node.val)16            if node.left:17                queue.append(node.left)18            if node.right:19                queue.append(node.right)20        result.append(level)21    return result

Use collections.deque, not a list. list.pop(0) shifts every remaining element, costing O(n) per pop and O(n²) overall; deque.popleft() is O(1).

Dry run on the example tree

In round 3, popping 5 pushes 7 onto the queue, but level_size was fixed at 3 before the round started, so 7 waits for round 4. The result is [[1], [2, 3], [4, 5, 6], [7]].

Complexity. Time is O(n): every node is pushed and popped exactly once. Space is O(w), the widest level. For a full tree the bottom level holds about n/2 nodes, so the worst case is O(n); for a chain it is O(1).

Approach 3: DFS that carries the depth

The output only needs each value in the right list, in left-to-right order within it. A preorder walk that passes the depth down does that too: it visits left before right, so within any one depth the values arrive left to right.

1def level_order_dfs(root: Optional[TreeNode]) -> list[list[int]]:2    """Same output from a preorder walk that carries the depth."""3    result: list[list[int]] = []45    def walk(node: Optional[TreeNode], depth: int) -> None:6        if node is None:7            return8        if depth == len(result):          # first node seen on a new level9            result.append([])10        result[depth].append(node.val)11        walk(node.left, depth + 1)        # left before right keeps each level in order12        walk(node.right, depth + 1)1314    walk(root, 0)15    return result

Time is O(n), and space is O(h) for the recursion instead of O(w) for the queue. That makes it the better choice for a wide, shallow tree — and the worse one for a deep chain, where it hits Python's recursion limit. BFS is the answer interviewers expect; mention the DFS version as the alternative.

Edge cases

• Empty tree. Return [] before creating the queue. Without that check, the queue holds None and the loop crashes on None.val.
• A single node. One round, result [[root.val]].
• A chain. One node per level; the queue never holds more than one node.
• Missing children on one side. Node 3 above has no left child. Only real children are pushed, so gaps never appear in the output.

Saying it in the interview

Follow-ups

• "Right side view." Keep only the last value of each level — level[-1], or the node popped when the loop index equals level_size - 1. For the example tree: [1, 3, 6, 7].
• "Zigzag order." Reverse every second level before appending it (or insert at the front of a deque on alternate rounds). Same O(n).
• "Minimum depth." Return the round number the moment you pop a leaf. BFS stops at the shallowest leaf, while DFS would explore every path.
• "Bottom-up levels" or "average of each level." Reverse the result at the end, or append sum(level) / len(level) instead of level.