Tree BFS and Level Order

Any tree question containing the words “level”, “depth”, “row”, “nearest”, or “width” is a breadth-first traversal in disguise. DFS visits a whole branch before its siblings, so it never has a level assembled in one place; BFS processes the tree in horizontal layers, which is exactly the shape those questions ask about.

There is one template. Once you can write it without thinking, roughly a dozen Medium problems become five-minute problems.

What you’ll learn

• The level-snapshot trick — the single line that turns a flat queue into “one iteration per level”.
• Why collections.deque and not a list (and what it costs if you get it wrong).
• The five mutations of the template that cover the whole level-order family.
• Four real LeetCode problems solved here in the browser: 102, 199, 103, and 111.

The cue

You are looking at tree BFS when…

The problem asks for something per level, or about distance from the root:

• “level order”, “each row”, “each level” — 102, 107, 515, 637
• “right/left side view”, “leftmost value in the last row” — 199, 513
• “minimum depth”, “shortest path to a leaf” — 111
• “maximum width”, “are these nodes cousins” — 662, 993
• “connect each node to its right neighbour” — 116, 117

Prefer DFS instead when the question is about a root-to-leaf path, a subtree property, or anything needing values returned up from children (path sums, diameter, validation). Those are the Tree DFS pattern.

Why minimum depth is BFS but maximum depth is DFS

For minimum depth, BFS can stop the instant it meets the first leaf — no other leaf can be shallower, because BFS visits in non-decreasing depth order. That is an early exit worth real time on a wide, shallow tree.

For maximum depth every node must be visited either way, so the simple recursion 1 + max(left, right) wins on clarity. Knowing why the two mirror-image problems want different traversals is a genuine discriminator in interviews.

The template

tree_bfs_template.py

from collections import deque
 
 
def level_order(root):
    if not root:                       # always handle the empty tree first
        return []
 
    result = []
    queue = deque([root])
 
    while queue:
        level_width = len(queue)       # <-- THE snapshot: freeze this level's size
        level = []
 
        for _ in range(level_width):   # consume exactly this level
            node = queue.popleft()
            level.append(node.val)
 
            if node.left:              # children form the NEXT level
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
 
        result.append(level)
 
    return result

Everything in the level-order family is this template with one of the inner lines changed.

The snapshot line is the whole pattern

level_width = len(queue) must be read before the inner loop starts. The loop appends children to the same queue, so len(queue) is changing as you iterate. Writing for _ in range(len(queue)) inline still works in Python — range() evaluates its argument once — but while queue: node = queue.popleft() without the snapshot silently flattens every level into one, and that is the single most common bug in this pattern.

How it works

Level by level, the queue holds exactly one complete level at the top of each while iteration. The inner for drains that level and, in the process, enqueues the entire next level behind it.

diagram BFS consumes the queue one full level per outer iteration mermaid

  graph TD
    A["3"] --> B["9"]
    A --> C["20"]
    C --> D["15"]
    C --> E["7"]

Visual intuition

Step through it with the queue on screen. The claim to verify for yourself: at the top of every outer iteration the queue contains exactly one complete level and nothing else. That is not obvious, and it is the only reason the snapshot line works.

treeBFS drains one whole level per outer iterationLC 102 · O(n) time, O(w) space

queue

3

1from collections import deque2 3def level_order(root):4    if not root: return []5    out, q = [], deque([root])6    while q:7        level = []8        for _ in range(len(q)):     # snapshot the level size!9            node = q.popleft()10            level.append(node.val)11            if node.left:  q.append(node.left)12            if node.right: q.append(node.right)13        out.append(level)14    return out

queue1

seedSeed the queue with the root. BFS uses a queue (first in, first out) — swap it for a stack and you get DFS instead.

Play‹›1/10⟲

Pause at each 'Level N starts' frame and read the queue. Its length there IS the level width -- which is why len(queue) must be snapshotted before the inner loop, never read inside it.

Dry run

Same tree, written out the way you should write it on a whiteboard:

Outer iteration	Queue at snapshot	level_width	Level emitted
1	[3]	1	[3]
2	[9, 20]	2	[9, 20]
3	[15, 7]	2	[15, 7]
4	[]	—	loop ends

Now the failure mode, so you recognise it instantly. Suppose the inner loop reads len(queue) live instead of snapshotting it:

Outer iteration	Queue	range(len(queue)) re-read each step	Level emitted
1	[3]	grows to 2 as 9 and 20 are enqueued	[3, 9, 20] ← wrong

One level bleeds into the next, and the output is a single flat list rather than a list of levels. If your LC 102 submission returns [[3,9,20,15,7]], this is why.

Time and space complexity

	Time	Space
Level-order BFS	$O(n)$ — every node enqueued and dequeued once	$O(w)$ where $w$ is the maximum level width

For a balanced tree the widest level holds about $n/2$ nodes, so space is $O(n)$. For a degenerate “linked list” tree the queue never holds more than one node, so space is $O(1)$ — the exact opposite of DFS recursion, which is $O(\log n)$ on a balanced tree and $O(n)$ on a degenerate one.

Use deque, not a list

list.pop(0) is $O(n)$ because every remaining element shifts left. Using a list as a queue turns this $O(n)$ traversal into $O(n^2)$ — fine on the samples, TLE on the real tests. collections.deque.popleft() is $O(1)$.

The variant map

Variant	What changes in the template	Canonical problem
Collect every level	The template verbatim	102 Binary Tree Level Order Traversal
One value per level	Keep only the last (or first, max, mean) node of each level	199 Right Side View · 515 Largest Value · 637 Average
Alternate direction	Build the level in a deque and appendleft on odd levels	103 Zigzag Level Order
Early exit	return mid-traversal on the first node meeting a condition	111 Minimum Depth
Carry extra state per node	Enqueue (node, depth) or (node, index) tuples instead of bare nodes	662 Maximum Width · 993 Cousins

The “one value per level” variant is worth watching, because the trick is smaller than people expect — there is no geometry involved at all:

treeRight side view is just 'the last node popped from each level'LC 199 · one line changed

queue

23

output1

1def right_side_view(root):2    if not root: return []3    out, q = [], deque([root])4    while q:5        n = len(q)6        for i in range(n):7            node = q.popleft()8            if i == n - 1:            # last of the level9                out.append(node.val)10            if node.left:  q.append(node.left)11            if node.right: q.append(node.right)12    return out

i0 of 0last?yesview1

level 01 is the last node dequeued from level 0, so it is the one you would see standing to the right of the tree. Record it.

Play‹›1/6⟲

Nothing about x-coordinates or rightmost children. The node you see from the right is whichever node happens to leave the queue last on its level -- so the only change to the template is an `if i == n - 1` test.

Reverse the output instead of reversing the traversal

For “bottom-up level order” (LC 107), do not try to traverse upwards. Run the normal template and return result[::-1]. Same for zigzag: build each level normally and flip alternate ones. Reversing at the end is always cheaper and clearer than fighting the traversal order.

Practice — real LeetCode problems

Each exercise is the real LeetCode problem with its real method signature. TreeNode and a build(...) helper (which turns LeetCode’s level-order array notation into an actual tree) are provided in the editor. Write the body, press Run, and match the expected output.

LC 102 — Binary Tree Level Order Traversal · Medium

Problem. Given the root of a binary tree, return the values of its nodes grouped by level, from left to right, one list per level.

Constraints. 0 <= number of nodes <= 2000, -1000 <= Node.val <= 1000.

Examples. [3,9,20,null,null,15,7] gives [[3],[9,20],[15,7]] · [1] gives [[1]] · [] gives []

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Push the root, then repeat: read how many nodes are in the queue (that is one full level), pop exactly that many, record their values, and enqueue their children.

Time $O(n)$ — each node is enqueued once and dequeued once. Space $O(w)$ for the queue, where w is the widest level.

The empty-tree guard is not optional: [] must return [], and without the guard deque([None]) would enqueue a None and crash on node.val.

Follow-ups you should expect: “Bottom-up (LC 107)?” — return out[::-1]. “Can you do it with DFS?” — yes: recurse with a depth argument and append to out[depth], creating the list when depth == len(out). It is $O(n)$ too, and worth mentioning as it shows you understand the traversals are interchangeable here; BFS is just the natural fit. “What about an N-ary tree (LC 429)?” — replace the two if node.left / node.right lines with for child in node.children.

LC 199 — Binary Tree Right Side View · Medium

Problem. Given the root of a binary tree, imagine standing to its right. Return the values of the nodes you can see, ordered top to bottom.

Constraints. 0 <= number of nodes <= 100.

Examples. [1,2,3,null,5,null,4] gives [1,3,4] · [1,null,3] gives [1,3] · [] gives []

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The visible node on each level is simply its last node in left-to-right order. So run the level template and record only the node at index width - 1.

Time $O(n)$. Space $O(w)$.

The trap in example 1

[1,2,3,null,5,null,4] has level 2 = [2, 3] and level 3 = [5, 4]. Node 5 is the left child of 2. A solution that walks “always go right, fall back to left” produces [1, 3, 4] here by luck, but breaks on trees where the deepest node hangs off a left branch that the right-spine walk abandoned early. The level-based answer is correct by construction; the greedy spine walk is not.

Follow-ups you should expect: “Left side view?” — record index 0 instead. “Do it with DFS?” — visit right child first and append when depth == len(out); that records the first node seen at each new depth, which is the rightmost. “Largest value per level (LC 515)?” — same shape, max() over the level instead of the last element.

LC 103 — Binary Tree Zigzag Level Order Traversal · Medium

Problem. Return the level-order traversal, but alternate direction per level: level 0 left-to-right, level 1 right-to-left, level 2 left-to-right, and so on.

Constraints. 0 <= number of nodes <= 2000.

Examples. [3,9,20,null,null,15,7] gives [[3],[20,9],[15,7]] · [1] gives [[1]] · [] gives []

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The traversal never changes. Only the assembly of each level flips: for right-to-left levels, prepend each value instead of appending.

Using a deque for the level makes prepending $O(1)$, so the whole thing stays $O(n)$. Building a list and calling level.insert(0, val) is $O(\text{level width})$ per insert and makes the level assembly $O(w^2)$ — a legitimate thing for an interviewer to poke at.

level.append(...) then level.reverse() on alternate levels is equally $O(n)$ overall and just as acceptable. What is not acceptable is trying to enqueue children in a different order to “naturally” produce zigzag — the direction flips every level, so child ordering cannot express it.

Time $O(n)$. Space $O(w)$.

Follow-ups you should expect: “Spiral starting right-to-left?” — initialise the flag to False. “Vertical order traversal (LC 314)?” — different pattern: enqueue (node, column) and bucket by column.

LC 111 — Minimum Depth of Binary Tree · Easy

Problem. Return the number of nodes along the shortest path from the root down to the nearest leaf. A leaf is a node with no children.

Constraints. 0 <= number of nodes <= 10^5.

Examples. [3,9,20,null,null,15,7] gives 2 · [2,null,3,null,4,null,5,null,6] gives 5 · [] gives 0

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

BFS dequeues nodes in non-decreasing depth order, so the first leaf it meets is a shallowest leaf. Return immediately — no need to finish the traversal.

Time $O(n)$ worst case, but only $O(\text{nodes above the shallowest leaf})$ in practice. On a tree with one short branch and a million-node deep branch, BFS returns almost instantly while a full DFS walks everything. Space $O(w)$.

The classic wrong answer

1 + min(minDepth(left), minDepth(right)) is wrong. For [1, 2] — a root with only a left child — the missing right subtree returns 0, giving 1, but the only leaf is at depth 2. A node with exactly one child is not a leaf, so a recursive solution must special-case it: if one side is missing, return 1 + minDepth(other side). This is the most-failed detail on LC 111, and the second test case ([2,null,3,null,4,null,5,null,6], a right-leaning chain) is there to catch exactly that.

Follow-ups you should expect: “Maximum depth (LC 104)?” — switch to DFS, 1 + max(left, right); there is no early exit to win so recursion is clearer. “Why not DFS here?” — the early exit; say it explicitly. “What if the tree is enormous and wide?” — BFS memory is $O(w)$ which can be huge; an iterative-deepening DFS trades time for $O(\text{depth})$ space.

LeetCode problem set

Generated from the problem database, so every entry carries its sheet membership and reported companies. Progress is saved in this browser.

17 problems

4 easy13 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○101Symmetric TreeeasyCompare each level against its own reverse (or two-pointer the queue)LeetCode Top Interview 150
• ○111Minimum Depth of Binary TreeeasyEarly exit on the first leaf; one-child nodes are not leaves
• ○637Average of Levels in Binary TreeeasyThe template with `sum(level) / len(level)`LeetCode Top Interview 150
• ○993Cousins in Binary TreeeasySame depth, different parent -- track the parent per node
• ○102Binary Tree Level Order TraversalmediumThe base templateNeetCode 150Blind 75LeetCode Top Interview 150amazonmetamicrosoftbytedance
• ○103Binary Tree Zigzag Level Order TraversalmediumFlip the assembly order, not the traversalLeetCode Top Interview 150
• ○107Binary Tree Level Order Traversal IImediumReverse the *result*, never the traversal
• ○116Populating Next Right Pointers in Each NodemediumPerfect tree -- do it in $O(1)$ space using the level you just linked
• ○117Populating Next Right Pointers in Each Node IImediumArbitrary tree -- the dummy-head trick per levelLeetCode Top Interview 150
• ○199Binary Tree Right Side ViewmediumKeep the last node per levelNeetCode 150LeetCode Top Interview 150
• ○314Binary Tree Vertical Order TraversalpremiummediumEnqueue `(node, column)` and bucket by column
• ○515Find Largest Value in Each Tree Rowmedium`max()` per level
• ○662Maximum Width of Binary TreemediumEnqueue `(node, index)`; width is `last - first + 1`
• ○863All Nodes Distance K in Binary TreemediumAdd parent links first, then BFS the tree as an undirected graph
• ○958Check Completeness of a Binary TreemediumEnqueue `None`s too; no real node may follow a `None`
• ○1161Maximum Level Sum of a Binary TreemediumTrack the level index of the best sum (1-indexed)
• ○1302Deepest Leaves SummediumKeep overwriting one running sum; the last level wins

Two tricks worth stealing from this list

Index arithmetic (662). Give the root index 0 and a node at index i children 2i and 2i+1. A level’s width is then last_index - first_index + 1, which handles the missing nodes for free without enqueueing placeholders.

The dummy head (117). When linking a level, keep a dummy node and a tail pointer for the level being built. tail.next = child; tail = child avoids every special case for “is this the first node on this level”. The same trick runs through the whole linked-list patterns phase.

Interview follow-ups

They ask	What they’re checking	The answer
“BFS or DFS here, and why?”	Whether you choose deliberately	Per-level or nearest-thing means BFS; path/subtree/return-value-upward means DFS
“What’s the space complexity?”	Precision	$O(w)$ = widest level, which is $O(n)$ balanced and $O(1)$ degenerate — the mirror image of DFS recursion
“Why deque and not a list?”	Python fluency	list.pop(0) is $O(n)$ and makes the traversal $O(n^2)$; deque.popleft() is $O(1)$
“Can you do 116 in $O(1)$ space?”	Whether you can drop the queue	Yes — once a level is linked, walk it via next pointers to link the level below; no queue needed
“Do it recursively”	Flexibility	Pass depth down and index into out[depth], appending a new list when depth == len(out)
“The tree has a billion nodes”	Practical limits	BFS holds a whole level in memory; if w is too large, iterative-deepening DFS trades time for $O(\text{depth})$ space

Edge-case checklist

• Empty tree (root is None) — must return [] / 0, and must not enqueue None.
• Single node — one level, and it is also a leaf. LC 111 must return 1.
• One-child nodes — the killer for LC 111: a node with one child is not a leaf.
• Completely one-sided tree ([1,null,2,null,3]) — every level has width 1; verifies your snapshot logic doesn’t assume two children.
• Duplicate values — never identify nodes by val; use the node objects themselves.
• Negative values — don’t initialise a per-level max to 0; use the first element or float("-inf").
• Very wide tree — mention the $O(w)$ queue memory before the interviewer does.

Self-check

pch.quizTag Tree BFS — self-check

1. Why must len(queue) be captured before the inner loop rather than read inside it?

   A For speed — len() on a deque is O(n) B Because the inner loop appends the next level to the same queue, so a live read would let levels bleed together C Because deque does not support len() during iteration D It makes no difference; both work
   pch.quizShowAnswer

   B — Because the inner loop appends the next level to the same queue, so a live read would let levels bleed together — The inner loop is simultaneously draining this level and filling the next one into the same container. Snapshotting the length freezes the boundary. Read it live and LC 102 returns one flat list instead of a list of levels.

2. Minimum depth of a binary tree: BFS or DFS?

   A DFS — the recursion 1 + min(left, right) is simplest B BFS — it can stop at the first leaf it meets, and no leaf can be shallower C Either; they have identical complexity in all cases D BFS, but only for balanced trees
   pch.quizShowAnswer

   B — BFS — it can stop at the first leaf it meets, and no leaf can be shallower — BFS visits in non-decreasing depth order, so the first leaf found is the shallowest — a genuine early exit on a wide, shallow tree. And note that naive `1 + min(left, right)` DFS is outright WRONG for minimum depth: a node with one child would report a depth through its missing child.

3. What is the space complexity of level-order BFS, and when is it worst?

   A O(log n), worst on a degenerate tree B O(h) where h is the height, worst on a balanced tree C O(w) where w is the widest level — so O(n) on a balanced tree and O(1) on a degenerate one D O(n) always
   pch.quizShowAnswer

   C — O(w) where w is the widest level — so O(n) on a balanced tree and O(1) on a degenerate one — The queue holds at most one level, so space tracks the maximum width. That is the exact mirror image of DFS recursion, which is O(log n) balanced and O(n) degenerate. Being able to state both directions is the discriminator here.

4. You need bottom-up level order (LC 107). What is the right move?

   A Traverse the tree upward from the leaves B Use a stack instead of a queue C Run the normal template and reverse the result list D Recurse and prepend at each depth
   pch.quizShowAnswer

   C — Run the normal template and reverse the result list — Change the assembly, never the traversal. `return result[::-1]` is O(levels) and obviously correct; fighting the traversal order is neither. The same principle covers zigzag — build each level normally, flip alternate ones.

5. Why deque rather than a plain list as the queue?

   A list has no append method B list.pop(0) is O(n) because every remaining element shifts, turning the traversal into O(n²) C deque uses less memory per element D list cannot hold tree nodes
   pch.quizShowAnswer

   B — list.pop(0) is O(n) because every remaining element shifts, turning the traversal into O(n²) — This is a Python-fluency check that costs real submissions. A list-as-queue passes the samples and TLEs on the full tests. collections.deque.popleft() is O(1).

Recall card

• Cue — the words level, row, depth, nearest, width, or “connect each node to its right neighbour”.
• Invariant — at the top of each outer iteration, the queue holds exactly one complete level.
• Template — deque, while queue:, snapshot n = len(queue), inner for _ in range(n) that pops one node and pushes its children.
• Complexity — $O(n)$ time, $O(w)$ space (widest level). Mirror image of DFS’s $O(h)$.
• Choose DFS instead when — the answer is a root-to-leaf path, a subtree property, or anything returned up from children. Minimum depth is BFS; maximum depth is DFS.

Recap

• Tree BFS = a deque, plus one snapshot line (level_width = len(queue)) that turns a flat queue into per-level iteration.
• The whole level-order family is that template with one inner line changed: keep all values, keep one value, flip the assembly order, exit early, or carry extra state per node.
• BFS for “per level” and “nearest”; DFS for paths and subtree properties. Minimum depth is BFS (early exit); maximum depth is DFS.
• $O(n)$ time, $O(w)$ space — and deque.popleft(), never list.pop(0).
• To reverse or zigzag, change the assembly, never the traversal.

Next: BST Patterns — what changes once the tree is ordered, and why an in-order walk is the only tool you need for a surprising number of problems.