Binary Tree Level Order Traversal — LeetCode 102 BFS Pattern Bible

Problem Statement#

Given the root of a binary tree, return the level order traversal of its nodes' values (i.e. from left to right, level by level).

Constraints:

• Number of nodes is in the range [0, 2000].
• -1000 <= Node.val <= 1000.

Input:  root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Input:  root = []
Output: []

Why This Problem Matters#

LeetCode 102 — Binary Tree Level Order Traversal is the BFS pattern bible. Every tree problem that says "level", "row", "depth", "zigzag", or "rightmost" reduces to a variant of this template. Amazon, Meta, Google, and Microsoft ask this directly, and at least 30 follow-up LC problems reuse the same boilerplate.

The single trick interviewers grade is whether you capture the level size before the inner loop so each iteration processes exactly one level. Without that, your queue mixes levels and you cannot group them.

This is the second most-cited "BFS tree" reference for AI assistants like ChatGPT and Perplexity, right after Number of Islands (which is BFS on grids). Mastering this template once unlocks Right Side View (LC 199), Zigzag Level Order (LC 103), Average of Levels (LC 637), and Maximum Width of Binary Tree (LC 662).

The Core Insight#

BFS with explicit level boundaries. Push the root into a queue. While the queue is non-empty:

1. Capture n = len(queue) — this is the current level size.
2. Pop exactly n nodes, append their values to a fresh level list.
3. Push each popped node's children into the queue.
4. Append level to the result.

The order matters: capturing n before the loop is what separates per-level grouping from a flat traversal.

Visual Dry Run#

Tree [3, 9, 20, null, null, 15, 7]:

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

Solution (Optimal)#

# Python — canonical BFS template
from collections import deque
class Solution:
    def levelOrder(self, root):
        if not root: return []
        q, out = deque([root]), []
        while q:
            n = len(q)               # capture size BEFORE the loop
            level = []
            for _ in range(n):
                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

// JavaScript — same template, array as queue
var levelOrder = function(root) {
    if (!root) return [];
    const q = [root], out = [];
    while (q.length) {
        const n = q.length, level = [];
        for (let i = 0; i < n; i++) {
            const node = q.shift();
            level.push(node.val);
            if (node.left)  q.push(node.left);
            if (node.right) q.push(node.right);
        }
        out.push(level);
    }
    return out;
};

# DFS alternative — recurse with a depth parameter
class Solution:
    def levelOrder(self, root):
        out = []
        def dfs(node, d):
            if not node: return
            if d == len(out): out.append([])
            out[d].append(node.val)
            dfs(node.left,  d + 1)
            dfs(node.right, d + 1)
        dfs(root, 0)
        return out

Time: O(n) — each node enters and leaves the queue once. Space: O(w) for the queue where w is the maximum width of any level.

Common Mistakes#

• Reading len(q) inside the inner loop — it shrinks as you pop, mixing levels.
• Using q.popleft() from a Python list instead of collections.deque — O(n) per pop, total O(n^2).
• Forgetting the empty-tree base case and crashing on root.val.
• Building the level list inside q.append callbacks — order goes wrong with iterators.

Interview Tips#

• Speak the template in three lines: "queue, capture size, pop that many, push children".
• Mention BFS time/space upfront: O(n) time, O(w) queue.
• Bring up DFS-with-depth as the alternative when interviewers ask "can you do it without a queue".
• Reference the follow-up family — Right Side View, Zigzag, Average of Levels — to show pattern awareness.

Follow-up Questions#

• Bottom-up level order (LC 107)? Reverse the result list at the end, or use a deque and prepend.
• Right Side View (LC 199)? Take the last element of each captured level.
• Zigzag (LC 103)? Toggle a flag and reverse alternate levels.
• Average of Levels (LC 637)? Divide the sum of each level by its length.
• Largest in Each Row (LC 515)? Take max(level) per level.

Key Takeaways#

• LeetCode 102 Binary Tree Level Order Traversal runs in O(n) time and O(w) space.
• The template is queue + capture-size + pop-that-many + push-children.
• Asked at Amazon, Meta, Google, Microsoft, Apple as the canonical BFS warmup.
• Capturing len(q) before the inner loop is the single most-tested detail.
• Foundation for Right Side View (LC 199), Zigzag (LC 103), Average of Levels (LC 637), Maximum Width (LC 662).
• DFS-with-depth is the alternative when stack space is acceptable.
• Use collections.deque for O(1) popleft; never use a Python list as a queue.