Tree Breadth-First Search (BFS) is an algorithm to traverse or search tree data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Core Idea:

  1. Queue: BFS is typically implemented using a queue to keep track of the nodes to visit.
  2. Level-by-Level: It explores all nodes at the current level before moving to the next level.
  3. Process:
    • Add the root node to the queue.
    • While the queue is not empty:
      • Dequeue a node.
      • Process the dequeued node (e.g., add its value to a list, check a condition).
      • Enqueue all of its children (from left to right, or in a specific order if required).

Common Scenarios & How it Works:

  1. Level Order Traversal (e.g., LeetCode #102): This is the most straightforward application. Collect all nodes at each level, often storing them in a list of lists.
    • To distinguish levels, you can get the size of the queue before processing a level. All nodes dequeued up to that size belong to the current level.
  2. Finding the Shortest Path in Unweighted Graphs/Trees: BFS is guaranteed to find the shortest path (in terms of the number of edges) from a source node to all other nodes because it explores layer by layer.
  3. Zigzag Level Order Traversal (e.g., LeetCode #103): Similar to level order traversal, but the order of nodes is reversed for alternate levels. This can be achieved by reversing the sublist for odd/even levels or by using a deque and adding/removing from different ends.
  4. Average of Levels in Binary Tree (e.g., LeetCode #637): Calculate the average value of nodes at each level.
  5. Minimum Depth of Binary Tree (e.g., LeetCode #111): Find the shortest path from the root to a leaf node. The first leaf node encountered during BFS gives the minimum depth.
  6. Maximum Depth of Binary Tree (e.g., LeetCode #104): While DFS is more intuitive for this, BFS can also find it by simply counting the number of levels.
  7. Populating Next Right Pointers in Each Node (e.g., LeetCode #116, #117): Connect nodes at the same level. During BFS, when processing a level, you can link the previously dequeued node (if any from the same level) to the current node.
  8. Right/Left View of a Binary Tree (e.g., LeetCode #199): For a right view, the last node processed at each level is part of the view. For a left view, it’s the first node.

Advantages:

  • Completeness: Guaranteed to find a solution if one exists.
  • Shortest Path: Finds the shortest path in terms_of number of edges in unweighted graphs/trees.
  • Simple Implementation: Relatively easy to implement using a queue.

When to Use:

  • When you need to traverse a tree level by level.
  • Finding the shortest path in an unweighted graph or tree.
  • Problems involving “levels” of a tree (e.g., level order traversal, average of levels, connecting nodes at the same level).
  • When exploring all nearby nodes before moving further away is beneficial.

Example LeetCode Problems:

  1. (#102) Binary Tree Level Order Traversal
  2. (#103) Binary Tree Zigzag Level Order Traversal
  3. (#104) Maximum Depth of Binary Tree (Often solved with DFS, but BFS is possible)
  4. (#107) Binary Tree Level Order Traversal II (Bottom-up level order)
  5. (#111) Minimum Depth of Binary Tree
  6. (#116) Populating Next Right Pointers in Each Node
  7. (#117) Populating Next Right Pointers in Each Node II
  8. (#199) Binary Tree Right Side View
  9. (#637) Average of Levels in Binary Tree
  10. (#994) Rotting Oranges (Graph BFS)