Loading...
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.
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:
Click any topic to jump in
Queue-based level-by-level traversal — the FIFO pattern that visits nearby nodes before distant ones.
Group tree nodes by depth using queue-size snapshots — the canonical BFS application on binary trees.
Direction, rightmost, and more
Alternate traversal direction per level — same BFS with a per-level reverse or a deque twist.
Capture the last node at each level — a one-line tweak that reveals the rightmost visible profile.
First-leaf-wins shortest path — why BFS beats DFS when the answer is close to the root.
Breadth First Search uses a queue (FIFO) to traverse a tree level by level. You start by enqueuing the root, then repeatedly dequeue a node, process it, and enqueue its children. This guarantees that you visit all nodes at depth d before any node at depth d+1.
The key insight for tree problems is level-aware BFS: at the start of each iteration, you record the current queue size --- that is exactly how many nodes belong to the current level. You then process exactly that many nodes, and any children enqueued during this batch belong to the next level.
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.
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.