Binary Tree Level Order Traversal — Queue Size Snapshot

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 many binary tree interview favorites. The single trick: 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.

Intuition

BFS uses a queue, and trees are graphs without cycles, so no visited set is needed. The key insight is the size snapshot: capture the queue length before processing each level so that children we enqueue do not bleed into the current level. Each iteration of the outer loop produces exactly one level’s values. A DFS variant works too — pass a depth index down and append to out[depth] — but the queue version is the most natural fit.

Explanation with 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]].

tree:                level groups:
     3             level 0: [3]
    / \            level 1: [9, 20]
   9  20            level 2: [15, 7]
      / \
     15  7

queue evolution (size taken at top of loop):
step 1: q=[3]        size=1  pop 3,  push 9,20
step 2: q=[9,20]     size=2  pop 9,  pop 20, push 15,7
step 3: q=[15,7]     size=2  pop 15, pop 7
step 4: q=[]         done

Code

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

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> out = new ArrayList<>();
    if (root == null) return out;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        out.add(level);
    }
    return out;
}

std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> out;
    if (!root) return out;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        std::vector<int> level;
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        out.push_back(level);
    }
    return out;
}

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).

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, 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, say “Same template, but I only keep the last node of each level.”

Related Problems

• Binary Tree Zigzag Level Order Traversal
• Binary Tree Right Side View
• Average of Levels in Binary Tree
• 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.