Tree BFS (Level Order)

At a glance

The instinct

Depth-first search dives down one branch and only comes back up later, so it scatters the nodes of one level across time. Breadth-first search uses a queue, which hands nodes back in exactly the order they were discovered: the whole of level 0, then all of level 1, then level 2. Whenever the question is phrased in terms of rows, depth, or "the first node you meet", BFS gives the answer in the order you need it, without extra bookkeeping.

Recognise it

Not this pattern if...

• The answer combines information from children up to the parent (height, diameter, path sums): that is Tree DFS.
• You need sorted order of a BST: that is in-order traversal.
• The "levels" are in a general graph with cycles: same idea, but you also need a visited set (graph BFS).

Memory hack

Analogy - boarding a ferry by rows. Passengers wait in a single queue. The usher counts how many are standing at the gate right now, lets precisely that many board as one row, and anyone who arrives while they board waits for the next sailing. Counting first is what keeps the rows clean.

Say it out loud in the interview:

1. "This is about levels, so I'll BFS with a queue, seeded with the root (guarding against a null root)."
2. "Each round I snapshot the size, pop that many, do the per-level work, and push non-null children."
3. "After the inner loop, I record the level result - first/last node, sum, list, or width."

How it works

Trace on the tree 3 -> (9, 20), 20 -> (15, 7):

Right side view takes the last value of each row (3, 20, 7). Zigzag reverses round 1 to [20, 9]. Minimum depth would stop at round 1 if 9 were a leaf.

flowchart TD
  A["queue = [root]"] --> B{"queue empty?"}
  B -->|no| C["n = queue.size()"]
  C --> D["pop n nodes, push their children"]
  D --> E["record level answer"]
  E --> B
  B -->|yes| F["return answer"]

Java template

import java.util.*;

class TreeNode {
    int val; TreeNode left, right;
    TreeNode(int v) { val = v; }
}

class TreeBfs {
    // Generic level-order skeleton.
    static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int n = queue.size();                  // freeze the row
            List<Integer> level = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);               // per-node work (i == n - 1 is the rightmost)
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            if (depth % 2 == 1) { /* zigzag: Collections.reverse(level); */ }
            result.add(level);                     // per-level work
            depth++;
        }
        return result;
    }

    // Width variant: carry a positional index, re-based per level to avoid overflow.
    static int maxWidth(TreeNode root) {
        if (root == null) return 0;
        Deque<Object[]> queue = new ArrayDeque<>();
        queue.offer(new Object[]{root, 0L});
        int best = 0;
        while (!queue.isEmpty()) {
            int n = queue.size();
            long first = (long) queue.peek()[1], last = first;
            for (int i = 0; i < n; i++) {
                Object[] cur = queue.poll();
                TreeNode node = (TreeNode) cur[0];
                long idx = (long) cur[1] - first;  // normalise so indices stay small
                last = idx;
                if (node.left != null) queue.offer(new Object[]{node.left, 2 * idx});
                if (node.right != null) queue.offer(new Object[]{node.right, 2 * idx + 1});
            }
            best = Math.max(best, (int) (last + 1));
        }
        return best;
    }
}

Complexity

• Time: O(n) - every node is enqueued and dequeued once.
• Space: O(w), where w is the widest level. For a complete tree the last level holds about n/2 nodes, so the worst case is O(n); for a skinny, list-like tree it is O(1). (DFS is the mirror image: O(h) stack.)

Variations

• Plain level order / bottom-up level order - collect rows; reverse the final list for bottom-up. Binary Tree Level Order Traversal.
• Pick one per row - first or last node of each round. Binary Tree Right Side View.
• Direction flip - reverse odd rows, or use a deque and add to the front. Binary Tree Zigzag Level Order Traversal.
• Sibling linking - keep a prev pointer within the round; an O(1)-space version walks the already-linked level above like a linked list. Populating Next Right Pointers in Each Node II.
• Positional index - heap-style indices 2i and 2i+1, re-based each level. Maximum Width of Binary Tree.
• Early exit - stop at the first level where a leaf or target appears. Minimum depth, nearest target.
• Multi-source / distance K - convert the tree to a graph (add parent links) and BFS from a start node.

Common mistakes

• Forgetting the root == null guard, then calling queue.offer(null) - ArrayDeque throws a NullPointerException.
• Pushing null children and not checking them after polling; either skip nulls at push time or handle them consistently (some "complete tree" checks push nulls on purpose).
• Using raw heap indices for width on deep, skewed trees: 2i + 1 doubles each level and overflows even a long after ~63 levels unless you re-base per level.
• Picking BFS for problems that need children's results first (diameter, balanced check) - you end up storing everything and reconstructing a DFS by hand.
• Reversing the queue itself for zigzag instead of just the collected row - this scrambles the order of the next level.

All practice problems

5 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.