LeetCode Binary Tree Level Order Traversal

LeetCode 102 — Binary Tree Level Order Traversal — is the friendly entry point to BFS on trees. The problem is small, but the template you learn here powers Zigzag Level Order, Right Side View, Average of Levels, and a handful of binary tree interview favorites. The single trick to remember: snapshot the queue size before processing each level.

The Problem

Given the root of a binary tree, return its level-order traversal as a list of lists, where each inner list holds the values of one level from left to right.

Brute Force

A naive idea is to compute the depth of each node with a helper, sort all nodes by depth, then group them. It works but pays an extra traversal and a sort. Worth describing only to dismiss.

def levelOrder(root):
    nodes = []
    def walk(node, depth):
        if not node:
            return
        nodes.append((depth, node.val))
        walk(node.left, depth + 1)
        walk(node.right, depth + 1)
    walk(root, 0)
    nodes.sort()
    out = []
    for depth, val in nodes:
        if depth == len(out):
            out.append([])
        out[depth].append(val)
    return out

This is O(n log n) for the sort with no real benefit.

Optimal Solution

Use a queue. At the top of each iteration, take the current queue size — that is the number of nodes on this level. Dequeue exactly that many, collect their values, and enqueue their children.

from collections import deque

def levelOrder(root):
    if not root:
        return []
    out = []
    q = deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            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

The for _ in range(len(q)) line is the whole trick. Capturing the size before the loop freezes the level boundary even as children get appended to the back.

A DFS version works too — pass a depth index down and append to out[depth]. Just as valid, often shorter, sometimes confusing to read.

Walk Through an Example

For the tree [3, 9, 20, null, null, 15, 7]:

• Queue starts as [3]. Size is 1. Process 3, append 9 and 20. Level: [3]. Queue: [9, 20].
• Size is 2. Process 9 (no children), then 20 (children 15 and 7). Level: [9, 20]. Queue: [15, 7].
• Size is 2. Process 15 and 7 (no children). Level: [15, 7]. Queue empty.

Result: [[3], [9, 20], [15, 7]].

Edge Cases

• Empty tree — return an empty list.
• Single node — return [[root.val]].
• A degenerate left- or right-skewed tree — every level has exactly one node, so the queue never grows beyond 1.
• A perfect binary tree of depth d — the last level has 2^(d-1) nodes, which dominates memory.

Complexity Analysis

Time is O(n) because every node is enqueued and dequeued exactly once. Space is O(w) where w is the maximum width of the tree. For a complete binary tree, w can approach n / 2 on the last level, so worst-case space is O(n). The brute-force sort version costs O(n log n) time for no improvement in space.

For more on traversal complexities and how they compare to graph BFS, the graphs introduction sets up the same vocabulary.

How to Explain It in an Interview

Open with the data structure: “BFS uses a queue, and trees are graphs without cycles, so we never need a visited set.” Then call out the size-snapshot: “I capture the queue length before processing each level so that the children we enqueue do not bleed into the current level.” Write the code. If pressed, mention DFS with depth as an alternative.

When the interviewer pivots to Zigzag (LeetCode 103), say “Same template, but I reverse alternating levels — or use a deque and append to either end based on the level parity.” When they pivot to Right Side View (LeetCode 199), say “Same template, but I only keep the last node of each level.”

Related Problems

• LeetCode 103 — Binary Tree Zigzag Level Order Traversal
• LeetCode 199 — Binary Tree Right Side View
• LeetCode 637 — Average of Levels in Binary Tree
• LeetCode 116 — Populating Next Right Pointers in Each Node

All four reuse the level-bounded BFS template with a one-line tweak.

Wrap up

Level Order Traversal is the BFS template you should be able to write without thinking, because half the binary-tree problem set is “do level order, but with a twist.” The size snapshot is the only piece that bites people under pressure — burn it into muscle memory. Then any twist the interviewer asks for becomes a one-line modification, and you can spend your time talking about the twist instead of debugging the base case.