Level-order (BFS)
Scenario
An organization wants to send a broadcast message layer by layer: CEO first, then all VPs, then all Managers, then all Engineers.
How do you traverse a tree row by row without skipping ahead to deep subtrees?
Why it exists
Problem: Depth-First Search (DFS) follows a single branch down to maximum depth before backtracking, making it inefficient when searching for nodes closest to the root.
Naive approach: Using DFS repeatedly with increasing depth limits, re-traversing upper levels multiple times.
Better idea: Use an explicit FIFO Queue to store nodes level by level. Processing nodes in First-In-First-Out order guarantees that all nodes at depth `d` are processed before any node at depth `d + 1`.
Mental model
Ripples spreading outward in a pond, processing every node at distance d before moving to distance d + 1.
Maintain a Queue initialized with the root node. In each step, dequeue the front node, process it, and enqueue its valid left and right children. To group output per level, snapshot the queue size `level_size = len(queue)` at the start of each level loop.
Repeated decision: dequeue the front node -- which of its children do I enqueue (both, one, none)?
Explanation
Breadth-First Search (BFS) traverses a tree layer by layer, moving horizontally across all nodes at the current depth before descending to the next depth level.
Algorithm Steps:
1. Initialize a FIFO queue with `queue = deque([root])` (if root is not None).
2. While `queue` is not empty:
a. Record current queue length: `level_size = len(queue)`.
b. Loop `level_size` times:
- Dequeue front node `curr = queue.popleft()`.
- Visit / record `curr.val`.
- If `curr.left` exists, `queue.append(curr.left)`.
- If `curr.right` exists, `queue.append(curr.right)`.
Why Queue Size Snapshot Works:
At the beginning of processing level `d`, the queue contains EXACTLY the nodes belonging to level `d`. By popping exactly `level_size` nodes, all children appended during that inner loop naturally form level `d + 1` for the next iteration.
Concrete Walkthrough:
Tree:
1
/ \
2 3
/ \
4 5
- Init: Queue = `[1]`
- Level 1: `level_size = 1`. Pop `1`. Enqueue `2` and `3`. Queue = `[2, 3]`. Level 1 output: `[1]`.
- Level 2: `level_size = 2`. Pop `2` (enqueue `4`, `5`). Pop `3`. Queue = `[4, 5]`. Level 2 output: `[2, 3]`.
- Level 3: `level_size = 2`. Pop `4`. Pop `5`. Queue empty. Level 3 output: `[4, 5]`.
Final Level-Order Result: `[[1], [2, 3], [4, 5]]`.
Level-Order Applications (Right Side View):
Because the inner level loop processes nodes left-to-right, the last node processed in each level loop is the rightmost node of that level. Collecting the final element of each level yields the tree's Right Side View (the nodes visible when viewing the tree from the right side).
Key points
- FIFO Invariant: The queue always contains nodes ordered strictly by non-decreasing depth.
- DFS vs BFS Space & Order: DFS uses implicit call-stack O(h) space (deep). BFS uses explicit queue O(w) space (wide, where w is max width).
- Shortest Distance Property: BFS visits the shallowest nodes first. The first time a target node is encountered in BFS, it is guaranteed to be at the minimum depth.
Pattern: Level-Order BFS
Recognition cues:
- level-by-level requirement
- shallowest node / minimum depth search
- queue data structure requirement
Failure signals
- Problem asks to process tree nodes level by level or row by row.
- Problem asks for the minimum depth or shallowest leaf node.
Engineering examples
Organizational Hierarchy Reporting
Display an org-chart UI grouped strictly by management reporting tier.
BFS level-order traversal groups employees naturally by their depth tier in the company hierarchy.
Network Broadcast / Web Crawler Scope
Crawl web pages or send network updates starting from a seed page out to k links distance.
BFS explores all immediate neighbors (distance 1) before exploring distance 2, maintaining strict distance bounds.
When not to use
- Tree path finding down to deep leaves when width is huge: If the tree is extremely wide (e.g. 100-way branching), BFS queue memory can explode compared to DFS stack memory.
Common mistakes
- Using a Stack instead of a Queue: Using a LIFO stack converts the algorithm back into Depth-First Search (DFS).
- Forgetting to snapshot queue length for level boundaries: If you process the queue without capturing `len(queue)` at the start of a level, level boundaries blur and you lose the 2D `[[level_1], [level_2]]` structure.
- Enqueuing null child nodes: Pushing `None` into the queue inflates queue size and causes AttributeError when calling `.val` or `.left` on dequeued items.
Recall questions
- What data structure is essential for implementing Breadth-First Search (BFS)?
- How do you separate nodes into individual levels during a level-order traversal?
- Why does BFS guarantee finding the minimum depth leaf first?
Questions & answers
Binary Tree Level Order Traversal: Return level-by-level node values as a list of lists.
Use BFS with a FIFO queue. In each iteration, capture level_size, pop level_size elements into a list, append their children to the queue, and append the list to the result.
Approach: Standard BFS level-order traversal with queue size snapshot.
Find the Right Side View of a Binary Tree.
Perform a level-order traversal. For each level, append the last dequeued node's value to the result list.
Approach: Level-order BFS; pick the rightmost element (last element of each level loop).
Interesting facts
- BFS on a tree requires no visited set because trees have no cycles. When generalized to graphs, adding a visited set is the only extra requirement.
Continue learning
Previous: Queue & deque
Previous: Binary tree & traversals
Next: BFS on graphs
Related: Queue & deque
Related: Binary tree & traversals
Related: BFS on graphs