Chapter 6: Breadth First Search
Master BFS traversal and its applications on binary trees. Learn how queue-based level-by-level exploration solves problems where DFS falls short, including level-order traversal, zigzag ordering, right side view, and finding minimum depth efficiently.
- Topics
- 5
- Demos
- 5
- Min read
- 25
Chapter Overview
Breadth First Search (BFS) explores a tree level by level, visiting all nodes at depth d before any node at depth d+1. While DFS dives deep into one branch before backtracking, BFS spreads wide across each level using a queue to maintain the frontier of nodes to visit next.
This level-by-level property makes BFS the natural choice for problems that involve layers, levels, or finding the shortest path. When you need to process nodes in order of their distance from the root, BFS gives you that guarantee for free.
The core BFS pattern is simple: start with the root in a queue, then repeatedly dequeue a node, process it, and enqueue its children. The variation that makes BFS truly powerful for tree problems is level-aware BFS, where you process one full level per iteration by tracking the queue size at each step.
This chapter covers:
- BFS Fundamentals: The queue-based traversal pattern and when to choose BFS over DFS
- Level-Order Traversal: Collecting all nodes grouped by their level
- Zigzag Level Order: Alternating the direction of traversal at each level
- Right Side View: Identifying the last visible node at each level
- Minimum Depth: Using BFS to find the shortest root-to-leaf path
Chapter Roadmap
Click any topic to jump in
BFS Fundamentals
Queue-based level-by-level traversal — the FIFO pattern that visits nearby nodes before distant ones.
Level-Order Traversal
Group tree nodes by depth using queue-size snapshots — the canonical BFS application on binary trees.
Direction, rightmost, and more
Zigzag Level Order
Alternate traversal direction per level — same BFS with a per-level reverse or a deque twist.
Right Side View
Capture the last node at each level — a one-line tweak that reveals the rightmost visible profile.
Minimum Depth
First-leaf-wins shortest path — why BFS beats DFS when the answer is close to the root.
Topics
5 topics in this chapter
A social network wants to suggest friends of friends before friends of friends of friends, and a game wants the enemy nearest to the player, not merely some enemy. In both cases, the order of the search matters: closer items must be examined before farther ones. The depth-first search of earlier chapters does the opposite, diving down one branch to the bottom before looking at a sibling that may be right next to the start.
The previous chapter, Backtracking, used DFS to enumerate every path through a state-space tree. Breadth-first search (BFS) visits nodes in order of distance from the start: first the root, then all nodes one edge away, then all nodes two edges away. The mechanism is a first-in, first-out queue. Removing a node from the front and appending its children to the back guarantees that everything at depth d is processed before anything at depth d + 1.
We first implement queue-based traversal on a binary tree and trace the queue step by step. Then we compare BFS with DFS, when each finds an answer sooner, and what each costs in memory, width versus height.
Definition
Breadth-first search traverses a tree or graph in order of distance from a start node. It keeps a FIFO queue, initialized with the start node, and repeatedly removes the front node, processes it, and appends its unvisited neighbours to the back. On a tree it visits every node once in O(n) time, using O(w) memory, where w is the maximum width of any level.
In this topic
- 1Queue-Based Traversal
- 2When BFS Beats DFS
Queue-Based Traversal
BFS relies on a queue (first-in, first-out) to track which nodes to visit next. You initialize the queue with the root, then loop: dequeue one node, process it, and enqueue its left and right children (if they exist). Because the queue preserves insertion order, nodes enqueued first (closer to the root) are processed before nodes enqueued later (deeper in the tree). This produces a level-by-level traversal without any explicit depth tracking. In Python, use collections.deque for O(1) popleft operations instead of a list, which would be O(n) for pop(0).
BFS maintains a FIFO queue representing the frontier of nodes to visit. Starting from the root, it repeatedly dequeues a node and enqueues its children, guaranteeing that any node at depth is dequeued before any node at depth . This is the invariant that makes BFS level-ordered. The time complexity is because each of the nodes is enqueued and dequeued exactly once, and each operation is with collections.deque (using a list would give per pop(0), pushing the total to ). Space is where is the maximum width of the tree — up to for a complete binary tree.
Implement basic BFS on a binary tree and print nodes in level order.
When BFS Beats DFS
BFS is the better choice when the answer lies close to the root or when you need to process nodes by their level. For minimum depth problems, BFS finds the first leaf encountered and immediately returns --- DFS would need to explore the entire tree to be sure it found the shallowest leaf. For level grouping problems, BFS naturally groups nodes by level, while DFS requires passing a depth parameter and managing a separate data structure. BFS also guarantees shortest path in unweighted graphs. However, BFS uses O(w) space where w is the maximum width of the tree, which can be up to n/2 for a complete tree. DFS uses O(h) space for the recursion stack, where h is the height.
BFS is optimal when the answer lies at shallow depth because it explores only nodes (where is branching factor) before finding it, while DFS may explore an entire subtree of depth . For minimum-depth problems, BFS terminates at the first leaf with worst-case cost , while DFS incurs in the worst case. The trade-off is space: BFS uses memory for the frontier while DFS uses only recursion stack. For wide shallow trees, BFS dominates; for narrow deep trees, DFS wins on memory.
Compare BFS and DFS approaches for finding whether a value exists near the root of a wide, shallow tree.
Related Problems on PixelBank
An org chart viewer wants to display a company one management layer per row: the CEO, then the CEO's direct reports, then theirs. A plain BFS visits people in exactly the right order, but it hands them over as one flat list, and nothing in that list says where one layer ends and the next begins, so the viewer cannot tell when to start a new row.
The previous topic, BFS Fundamentals, showed that the queue processes nodes in order of depth. Level-order traversal adds one observation that turns the flat order into groups: at the moment a level begins, the queue contains exactly the nodes of that level and nothing else. Recording len(queue) at that moment, then removing exactly that many nodes, processes one whole level while the children appended along the way wait for the next round. This level-size snapshot is the pattern the rest of this chapter builds on.
We first implement the grouped traversal, returning a list of lists, and trace the queue across levels. Then we produce the levels bottom-up, from the leaves to the root, and compare building the answer in reverse with reversing it once at the end.
Definition
Level-order traversal returns the values of a tree grouped by depth, as a list whose i-th entry lists the nodes at depth i from left to right. It is BFS with a level-size snapshot: at the start of each round, record the queue length k, remove exactly k nodes, and append their children. It runs in O(n) time and O(w) extra space.
In this topic
- 1Level Grouping with Queue Size
- 2Bottom-Up Level Order
Level Grouping with Queue Size
The core technique for level-order traversal is recording len(queue) at the start of each level. This snapshot tells you exactly how many nodes belong to the current level. You then dequeue exactly that many nodes in a for-loop, appending their values to a temporary list. Any children you enqueue during this loop belong to the next level and will be counted on the next iteration. This approach works because of a key invariant: at the start of each outer loop iteration, the queue contains exactly the nodes of one level.
The level-aware BFS invariant is: at the start of each outer iteration, the queue contains exactly the nodes at the current level . Taking as a snapshot, we dequeue exactly nodes, and any children enqueued during this batch belong to level . This works because each node is processed exactly once, and level- children always come from level- parents. Total work is , giving time.
Given a binary tree, return its level-order traversal as a list of lists.
Bottom-Up Level Order
A common variation asks for the levels in reverse order --- from leaves up to the root. The approach is identical to standard level-order traversal, but you reverse the final result. Alternatively, you can insert each level at the beginning of the result list, though this is O(n^2) with a Python list. The most efficient approach is to collect levels normally and call result.reverse() or result[::-1] at the end. This is a O(1) extension of the standard pattern, but it appears frequently in interviews to test whether you understand the structure well enough to adapt it.
Reversing a list of level-lists at the end is — the reversal swaps list pointers, not their contents. Alternatively, inserting each new level at the front of a Python list costs total because each insert(0, ...) shifts all previous levels right. Using collections.deque.appendleft reduces this back to . The BFS itself remains ; only the output assembly differs. This is a textbook example of why the final reversal approach (collect forward, then [::-1]) is preferred.
Given a binary tree, return its bottom-up level-order traversal.
Related Problems on PixelBank
A tree-printing tool wants to draw each level as a snake, left to right on the first row, right to left on the next, then left to right again, so the reader's eye never jumps back across the page. The same back-and-forth order appears in boustrophedon scans of images and in some printer head paths. Getting the order right on alternate levels is the whole difficulty.
The previous topic, Level-Order Traversal, grouped nodes by depth with the level-size snapshot. Zigzag traversal keeps exactly that machinery and changes only how each finished level is stored. The tempting approach is to change the traversal itself, pushing right children before left children on odd levels, but reversing the enqueue order does not reverse the next level; it scrambles the levels below it. The safe approach leaves the queue alone, always left to right, and reverses the collected values of every other level, or inserts them at the front of a deque.
We first implement the flag-and-reverse version and show why the reversal adds only O(n) total work. Then we build each level in a deque, appending on one side or the other, and compare the two approaches for clarity and cost.
Definition
Zigzag, or spiral, level-order traversal returns the values of a tree level by level, alternating direction: left to right on even depths and right to left on odd depths. It is level-order traversal with the queue processed left to right as usual and the collected values of every odd level reversed. The traversal remains O(n) time and O(w) extra space.
In this topic
- 1Alternating Direction with a Flag
- 2Deque-Based Insertion Alternative
Alternating Direction with a Flag
The simplest approach uses a boolean flag left_to_right that toggles after each level. When the flag is True, you append the level list as-is. When False, you reverse it before appending. This keeps the core BFS logic unchanged --- you always dequeue left child before right child --- and only modify how you store the collected values. The alternative of using two stacks or changing enqueue order is more complex and error-prone. Time complexity remains O(n) because reversing a level of size k is O(k), and summing across all levels gives O(n) total.
Zigzag traversal alternates between left-to-right and right-to-left at each level. The simplest approach is to run standard BFS and reverse every other level's list before appending: total reversal work is , so total time stays . A boolean flag toggles after each level, acting as the parity bit . The key insight: the BFS traversal order is unchanged — only the output order per level is flipped. Children are still enqueued left-to-right, preserving the standard level invariant.
Given a binary tree, return its zigzag level-order traversal.
Deque-Based Insertion Alternative
Instead of reversing the collected list, you can use a deque for the current level and insert at the front or back depending on direction. When left_to_right is True, append to the right of the deque. When False, appendleft to insert at the front. This avoids the explicit reverse step, but the asymptotic complexity is the same. The deque approach is slightly more elegant because it avoids creating a reversed copy, but the flag-and-reverse approach is easier to understand and less prone to off-by-one errors.
Using a collections.deque for each level's result list avoids the post-hoc reversal: on even levels, appendright in insertion order; on odd levels, appendleft to build the list backwards in one pass. Both operations are , so total time is with no wasted work. This is mathematically equivalent to the flag-based approach but saves a constant factor by eliminating the reversal step — useful when you care about wall-clock performance on large trees.
Implement zigzag traversal using deque-based insertion instead of reversing.
Related Problems on PixelBank
Stand to the right of a tree drawn on a wall and look left: at each height you see exactly one node, the rightmost one, and every other node on that level hides behind it. The right side view asks for those visible nodes from top to bottom. The catch is that a visible node need not be a right child. If the right part of the tree is short, a deep node in the left subtree can be the only node at its level, so it shows through.
The previous topic, Zigzag Level Order, changed how each level's values were stored. Here each level contributes a single value, its last node, and the level-size snapshot tells you exactly when that node is being processed. Walking down right-child pointers alone fails as soon as the right subtree ends early, because it never sees the deeper left-side nodes that are visible from the right.
We first solve it with level-aware BFS, keeping the last node of each level. Then we solve it with DFS that visits the right child before the left and records the first node seen at each new depth, and compare the memory the two approaches use.
Definition
The right side view of a binary tree is the list, from the root downward, of the rightmost node at each depth. With level-order BFS it is the last node processed in each level; with DFS that explores right before left, it is the first node reached at each new depth. Both approaches visit every node once, in O(n) time.
In this topic
- 1Last Node Per Level
- 2DFS Alternative for Right Side View
Last Node Per Level
Using level-aware BFS, you process all nodes at each level from left to right. The last node dequeued in each level is the rightmost node --- the one visible from the right side. You can track this by checking if the current node is the last in the for-loop (i == level_size - 1), or simply overwrite a variable with each node's value and use the final value after the loop ends. Both approaches are O(n) time and O(w) space. This problem demonstrates that BFS naturally provides positional information (first, last, middle) within each level without any extra data structures.
The right-side view is the set . In level-aware BFS, when processing the -th node out of nodes at level , the condition identifies the rightmost node. This gives exactly one node per level, so the output has size (one per level from root to deepest). Total time is — we still visit every node, we just cherry-pick one per level. Enqueuing left-child-first ensures the last dequeued node is the rightmost, matching the visual 'right side' view.
Given a binary tree, return the values of nodes visible from the right side.
DFS Alternative for Right Side View
While BFS is the natural fit, you can also solve right side view with DFS. The trick: visit the right subtree before the left subtree. Maintain a list of visible nodes. At each depth, if the list length equals the current depth, this is the first node encountered at this depth (which is the rightmost, since we visit right first). This DFS approach uses O(h) space for the recursion stack instead of O(w) for the BFS queue. For a balanced tree, h = log(n) and w = n/2, so DFS uses less space. For a skewed tree, h = n and w = 1, so BFS uses less space.
DFS can solve this with preorder-right-first recursion: visit root, then right child, then left child. Maintain a result list and append node.val only when depth == len(result) — i.e., when we are the first to reach this depth. Since right is explored first, the first node at any new depth is by construction the rightmost. Time is , space is recursion stack versus BFS's queue. For balanced trees while , so DFS is asymptotically more memory-efficient here.
Implement right side view using DFS (right-first traversal).
Related Problems on PixelBank
A customer-support decision tree routes each caller through questions until an answer is reached, and the team wants the fewest questions any caller can face. That is the distance from the root to the nearest leaf. It sounds like the mirror image of the maximum depth from the previous chapter, but replacing max with min in that recursion gives wrong answers, and the fastest method is not recursive at all.
The previous topic, Binary Tree Right Side View, used the level structure of BFS to pick one node per level. Minimum depth uses the same structure to stop early. BFS reaches the levels in increasing order, so the first leaf it removes from the queue is at the smallest depth, and the search can return immediately, ignoring everything deeper. DFS must, in general, explore every branch before it knows none has a shallower leaf. This is the tree version of the rule that BFS finds shortest paths in unweighted graphs, which the next chapter develops.
We first implement the early-exit BFS and count how many nodes it skips. Then we fix the DFS version, whose naive form treats a node with one missing child as a leaf.
Definition
The minimum depth of a binary tree is the number of nodes on the shortest path from the root to a leaf, a node with no children; the empty tree has minimum depth 0. BFS finds it by returning the depth of the first leaf dequeued. A node with only one child is not a leaf, so its missing child must not count as a path.
In this topic
- 1BFS for Shortest Path in Trees
- 2DFS Pitfall: Nodes with One Child
BFS for Shortest Path in Trees
BFS processes nodes in order of increasing depth. The first leaf encountered during BFS is, by definition, at the minimum depth. This is the same principle that makes BFS optimal for shortest path in unweighted graphs. When BFS dequeues a node and discovers it is a leaf (no left or right child), you can immediately return the current depth. No further exploration is needed. DFS cannot make this guarantee because it fully explores one branch before moving to the next --- the shortest path might be in a branch it has not yet visited. For a tree with n nodes where the shallowest leaf is at depth d, BFS visits at most O(2^d) nodes (all nodes up to level d). DFS visits O(n) nodes in the worst case.
Minimum depth is the length of the shortest root-to-leaf path. BFS processes nodes in order of their depth, so the first leaf encountered is at the minimum depth . Total work before termination is , but in practice much less — we stop as soon as we find any leaf. This is optimal: any algorithm must examine at least one leaf, and BFS examines exactly the leaves within the minimum-depth level. Compare to DFS, which must explore entire subtrees to be sure no shallower leaf exists.
Find the minimum depth of a binary tree using BFS.
DFS Pitfall: Nodes with One Child
A common mistake in the DFS approach is treating a node with one child as a leaf. If a node has only a left child and no right child, its minimum depth is NOT 1 --- you must continue down the existing child. The minimum depth requires reaching an actual leaf (no children at all). BFS handles this naturally because it only returns when it finds a true leaf. In DFS, you must add explicit checks: if one child is None but the other is not, only recurse into the existing child. This edge case frequently trips up candidates who write min(minDepth(left), minDepth(right)) + 1 without checking for None children.
A common DFS bug: return 1 + min(depth(left), depth(right)) for a node with only one child returns , incorrectly treating the null child as a leaf. The correct handling: if exactly one child is null, recurse only on the non-null child; if both are null, the current node is a leaf (depth 1). The recurrence is: if is a leaf, if only one child, if two children. This case analysis is why BFS is cleaner for this problem.
Show the pitfall of naive DFS and the correct DFS approach for minimum depth.