Breadth-First Search (BFS) in Trees

Objective: Traverse nodes layer by layer (level order), prioritizing nodes closest to the root.

1. Overview of BFS

• Key Idea: Process nodes level by level (root → children of root → grandchildren, etc.).
• Data Structure: Uses a queue (FIFO) to track nodes to visit.
• Applications:
  • Find shortest paths in unweighted graphs.
  • Level-order traversal for hierarchical data.
  • Social network friend recommendations (degrees of separation).

2. BFS Process

Example Tree:

      4
     / \\
    3   6
   /   / \\
  2   5   7

Step-by-Step Traversal:

1. Level 0 (Root):
   • Process 4.
   • Add its children (3, 6) to the queue.
2. Level 1:
   • Process 3 → add its left child (2).
   • Process 6 → add its children (5, 7).
3. Level 2:
   • Process 2, 5, 7 (no children).Output: 4, 3, 6, 2, 5, 7

3. Algorithm Implementation

Python Code

from collections import deque

def bfs(root):
    if not root:
        return
    queue = deque([root])  # Initialize queue with root
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            print(node.val, end=" ")
            # Add children to queue (left to right)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

Key Steps: