Introduction to Tree Breadth First Search Pattern

Tree BFS solves any "level by level" question by pushing nodes into a FIFO queue in the order they're discovered, so a node is never processed before any node closer to the root — the queue's insertion order is the level order, because a node's children are enqueued only after the node itself has been dequeued.

Recognize the pattern

• Problem mentions "level order", "level by level", "per-level", "zigzag", "level averages", or "minimum depth / shortest path in an unweighted tree or grid".
• You need to group nodes by distance from the root, or find the first node satisfying some property (BFS finds it in the fewest hops).
• You need the width or rightmost/leftmost view of a level — anything that depends on horizontal structure at a fixed depth.
• Contrast with DFS tells: "root-to-leaf path", "subtree sum", "ancestor/descendant" — those want depth-first recursion, not a queue.

Brute force vs optimal

Brute force: recursive DFS that tracks depth and appends each value into a List<List<Integer>> indexed by depth. Correct, but it recomputes the level from a passed-in depth parameter and needs care to pre-size the outer list dynamically; for pure "level order" style problems (widths, right-side view, min depth) it also loses the natural queue boundary between levels, making early termination (e.g. minimum depth) awkward — you must fully explore before knowing the level count. Cost: O(n) time, O(h) extra recursion stack (h = height).

Optimal (iterative BFS): use a queue, and snapshot queue.size() at the start of each round to know exactly how many nodes belong to the current level before enqueuing their children. This makes level boundaries explicit and lets you short-circuit the moment a level-based condition is met (e.g. minimum depth stops at the first leaf found). Cost: O(n) time, O(w) space where w is the maximum level width.

Complexity from first principles

Every node is enqueued exactly once and dequeued exactly once — 2n queue operations — so total work is O(n) time. Each operation is O(1): a linked-list-backed queue (e.g. Java's LinkedList used as a Queue) gives O(1) worst-case per operation, while an array-backed circular-buffer queue gives O(1) amortized per operation (occasional resize).

The queue never holds more nodes than exist on the single widest level, because a level's nodes are fully drained before their children (the next level) are pushed; hence O(w) space, where w = max nodes at any depth. This bound depends entirely on shape: a completely skewed tree (every node has at most one child) is the best case for space — the queue never holds more than one node at a time, so O(1) space. A complete binary tree is the worst case — its bottom level alone holds about n/2 nodes, so O(n) space. Both are the same O(n) time, but they sit at opposite ends of the space spectrum.

Worked example

Problem: sum all node values in the tree [10, 5, 3, 7, null, null, 9] (root 10; left child 5; right child 3; 5's left child 7; 3's right child 9).

Queue empties with sum = 34, matching the expected output.

Pitfalls

• Forgetting to snapshot queue.size() before the inner loop — mixing two levels together and breaking per-level logic (widths, zigzag, right-side view).
• Enqueuing a null child directly instead of checking for null first, causing a NullPointerException on dequeue.
• Using java.util.Stack where a queue is needed (LIFO reverses sibling order): Stack extends Vector and implements List, not Queue or Deque — it has no built-in FIFO API at all, so reaching for it here is doubly wrong. For a queue in Java use LinkedList, ArrayDeque, or Queue<TreeNode>.
• Recomputing depth via recursion when the problem explicitly needs early termination per level (e.g., minimum depth) — DFS must explore the entire subtree first, wasting work BFS avoids.

When to use / when not — trade-offs vs DFS

Use BFS when the problem is inherently level-shaped (level order, level averages, zigzag, right-side view) or needs the shortest path / minimum depth in an unweighted tree or graph, since BFS guarantees the first time you reach a target it's via the fewest edges. A telltale variant is "all nodes at distance K from a given target node" (LeetCode 863): the trick is that a tree edge only points parent→child, so first do one DFS/BFS pass to build a child → parent map, then run BFS outward from the target treating each node's neighbors as {left, right, parent} — after K levels of that BFS, the queue holds exactly the answer. It is still BFS-for-shortest-hops; you just repaired the tree into an undirected graph first.

Prefer DFS when the problem is path- or subtree-shaped (root-to-leaf sums, diameter, LCA, subtree aggregates) — DFS's O(h) space beats BFS's O(w) space on wide, shallow trees, and recursion maps directly onto path accumulation without extra bookkeeping.

Trade-off in one line: BFS spends O(w) space to get level structure and shortest-path guarantees for free; DFS spends O(h) space and gets natural path/subtree composition for free.

Java: level-order sum (queue-size snapshot idiom)

int sumTree(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int sum = 0;
    while (!queue.isEmpty()) {
        int levelSize = queue.size(); // freeze current level's count
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            sum += node.val;
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return sum;
}

Takeaways

• A queue's FIFO order naturally enforces level-by-level processing: children go in only after their parent comes out.
• Snapshot queue.size() at the top of each round to make level boundaries explicit — this single line unlocks zigzag, per-level aggregation, and early exit.
• Time is always O(n); space is bounded by the widest level, O(w) — a skewed tree is the best case (O(1)), a complete binary tree is the worst case (O(n)).

Recall: Why does snapshotting queue.size() before the inner loop matter, and what breaks if you skip it?

Pattern derived from standard BFS/level-order traversal technique; problem instance adapted from the source binary-tree-sum walkthrough.