Breadth First Search (BFS) in Trees

# CHAPTER 7

Breadth First Search (BFS) in Trees #

1. Introduction #

2. Learning Objectives #

• Understand the horizontal "Level by Level" scanning philosophy of BFS.

• Define how a FIFO Queue mechanically enforces Level Order traversal.

• Write Iterative BFS algorithms in multiple coding languages.

• Differentiate between the space complexities of BFS and DFS.

3. The Core Concept: The Queue (FIFO) #

When BFS encounters a node:

1. 1. It processes the node.

1. 2. It pushes the Left child to the absolute Back of the Queue.

1. 3. It pushes the Right child to the absolute Back of the Queue.

4. Step-by-Step Level Order Traversal #

        A (Level 0)
       / \
      B   C (Level 1)
     / \   \
    D   E   F (Level 2)

Execution Trace:

1. 1. Enqueue the Root A. Queue: [A].

1. 2. Dequeue A. Print A. Enqueue its children B, C. Queue: [B, C].

1. 3. Dequeue B. Print B. Enqueue its children D, E. Queue: [C, D, E]. *(Notice C is next in line! The algorithm sweeps horizontally!)*

1. 4. Dequeue C. Print C. Enqueue its child F. Queue: [D, E, F].

1. 5. Dequeue D. Print D. No children. Queue: [E, F].

1. 6. Dequeue E. Print E. No children. Queue: [F].

1. 7. Dequeue F. Print F. Queue empty. Algorithm halts.

*Output:* A -> B -> C -> D -> E -> F. Flawless horizontal Level Order scanning!

5. Code Execution (Iterative BFS) #

Java:

import java.util.LinkedList;
import java.util.Queue;

class BFS_Traversal {
    void printLevelOrder(Node root) {
        if (root == null) return;
        
        Queue<Node> queue = new LinkedList<>();
        queue.add(root); // Enqueue root
        
        while (!queue.isEmpty()) {
            Node tempNode = queue.poll(); // Dequeue front node
            System.out.print(tempNode.data + " ");
            
            // Enqueue Left Child
            if (tempNode.left != null) {
                queue.add(tempNode.left);
            }
            
            // Enqueue Right Child
            if (tempNode.right != null) {
                queue.add(tempNode.right);
            }
        }
    }
}

Python:

from collections import deque

def level_order_traversal(root):
    if root is None:
        return
    
    queue = deque([root]) # Use deque for fast O(1) pops
    
    while len(queue) > 0:
        node = queue.popleft() # Dequeue front node
        print(node.val, end=" ")
        
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)

6. Complexity Analysis #

• Time Complexity: $O(N)$. Every single node is mathematically dequeued and evaluated exactly once.

• Space Complexity (The Danger Zone): BFS requires horrific amounts of memory for extremely wide trees. At the deepest level of a perfect binary tree, exactly half of the entire tree's nodes reside on the bottom row. The Queue must aggressively store all $N/2$ nodes simultaneously in active RAM. Therefore, Space Complexity evaluates to $O(N)$ (technically $O(W)$ where $W$ is maximum width).

7. Common Mistakes #

• Using a standard Array/List as a Queue: In Python, using list.pop(0) takes sluggish $O(N)$ time because the entire array must shift left. You must use collections.deque to achieve the required $O(1)$ fast queue extraction, or your massive BFS algorithm will violently degrade to $O(N^2)$ execution speed!

8. Exercises #

1. 1. Trace the explicit state of the Queue array at every single step when executing BFS on a Degenerate (straight-line) Binary Tree. What is the maximum size the Queue ever reaches?

1. 2. Why does BFS natively and flawlessly guarantee the shortest geometric path to a node, while DFS completely fails at this metric?

9. MCQs with Answers #

11. Interview Preparation #

• *Algorithmic Architecture:* "You are designing an AI for a Chess game. It needs to evaluate the board 3 moves ahead to find an instant checkmate. Do you use BFS or DFS?" *(Answer: BFS! A game-tree branches infinitely. DFS will dive a million moves deep into a random, useless trajectory and time out. BFS checks all 1-move wins, then all 2-move wins, guaranteeing the fastest possible victory discovery!)*

12. Summary #

13. Next Chapter Recommendation #