Master DSA: Breadth-First Search (BFS) & Tree Level Order Traversal

Breadth-First Search (BFS) is a fundamental tree and graph traversal algorithm that explores nodes level by level. Unlike Depth-First Search (DFS), which dives deep into a branch before backtracking, BFS systematically sweeps across the breadth of the tree. This guide explores the core mechanics of BFS, its queue-based implementation, and its application to classic coding interview problems.

1. The Core Mental Model: DFS vs. BFS

To understand Breadth-First Search (BFS), it is helpful to contrast it directly with Depth-First Search (DFS).

Consider the following binary tree structure:

Depth-First Search (DFS)

In DFS, the traversal goes deep down a single path before backtracking to explore other branches. Typically, it starts at the root, traverses down the leftmost path to the leaf, and then backtracks.

• Traversal Order: 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
• Behavior: Prioritizes depth over breadth.

Breadth-First Search (BFS)

In BFS, the traversal visits all nodes at the current depth level before moving down to the next level.

• Traversal Order: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
• Behavior: Prioritizes breadth, processing the tree level by level:
  • Level 1: [1]
  • Level 2: [2, 3]
  • Level 3: [4, 5, 6, 7]

2. The Queue-Based Level Order Traversal Pattern

The standard data structure used to implement BFS is a Queue. A queue operates on a FIFO (First-In, First-Out) basis: elements are inserted at the rear and removed from the front.

The Level-Boundary Challenge

If we simply enqueue and dequeue nodes continuously, we lose track of where one level ends and the next begins. To group nodes by their respective levels, we must freeze the queue's size at the start of each level's processing.

The "Size-Snapshot" Pattern

1. Get the size of the queue at the start of the level iteration: size = queue.size().
2. This size represents the exact number of nodes present at the current level.
3. Run a nested for loop exactly size times.
4. During these size iterations, dequeue the current node, record its value, and enqueue its children. Any newly added children are placed at the back of the queue and will not be processed during the current level's loop.

3. Problem 1: Binary Tree Level Order Traversal

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes' values (i.e., from left to right, level by level) as a list of lists.

Step-by-Step Execution Walkthrough

Let's trace the queue state and output list for our sample tree:

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

1. Initialization: Enqueue the root node [1].
2. Level 1:
   • Queue size = 1.
   • Dequeue 1. Add 1 to the Level 1 list.
   • Enqueue children of 1: Left child 2, Right child 3.
   • Queue state: [2, 3].
   • Result: [[1]].
3. Level 2:
   • Queue size = 2. (Only nodes 2 and 3 will be processed in this level).
   • Dequeue 2. Add 2 to the Level 2 list. Enqueue children of 2: 4 and 5.
   • Dequeue 3. Add 3 to the Level 2 list. Enqueue children of 3: 6 and 7.
   • Queue state: [4, 5, 6, 7].
   • Result: [[1], [2, 3]].
4. Level 3:
   • Queue size = 4.
   • Dequeue 4, 5, 6, and 7 one by one. Since they have no children, nothing is enqueued.
   • Result: [[1], [2, 3], [4, 5, 6, 7]].

Java Implementation

import java.util.*;

public class LevelOrderTraversal {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        
        // Base Case
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                
                // Enqueue left child
                if (node.left != null) {
                    queue.add(node.left);
                }
                // Enqueue right child
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            // Add the completed level to our final result
            result.add(currentLevel);
        }
        
        return result;
    }
}

4. Complexity Analysis of BFS

Understanding the time and space complexity of BFS is critical for technical interviews.

Time Complexity: $O(N)$

• We visit each node in the binary tree exactly once.
• For each node, the queue operations (enqueue and dequeue) take $O(1)$ constant time.
• Thus, the total time complexity is linear with respect to the number of nodes $N$.

Space Complexity: $O(W)$ or $O(N)$

• The space complexity is determined by the maximum number of nodes stored in the queue at any given time.
• This corresponds to the maximum width ($W$) of the binary tree.
• In a balanced binary tree, the lowest level contains approximately half of the total nodes:

• Therefore, in the worst-case scenario (a fully balanced tree), the queue will hold up to $O(N)$ nodes at the deepest level.

5. Problem 2: Binary Tree Zigzag Level Order Traversal

Problem Statement

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level, and alternate between the two).

Example Tree:
      3
     / \
    9  20
      /  \
     15   7

Expected Output: [[3], [20, 9], [15, 7]]

The Directional Flag Strategy

To implement this without changing the core BFS queue traversal order, we can use a boolean flag isForward to control how we insert elements into the current level's list:

• If isForward is true, we append elements to the end of the list (add last).
• If isForward is false, we insert elements at the beginning of the list (add first). This reverses the order of the level's output list.
• Toggle the flag (isForward = !isForward) at the end of each level.

Java Implementation

import java.util.*;

public class ZigzagLevelOrder {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        boolean isForward = true;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            // Using LinkedList to support efficient addFirst / addLast operations
            LinkedList<Integer> currentLevel = new LinkedList<>();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                
                if (isForward) {
                    currentLevel.addLast(node.val);
                } else {
                    currentLevel.addFirst(node.val);
                }
                
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            
            result.add(currentLevel);
            // Toggle direction for the next level
            isForward = !isForward;
        }
        
        return result;
    }
}

6. Problem 3: Minimum Depth of a Binary Tree

Problem Statement

Find the minimum depth of a binary tree. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Why BFS is Superior to DFS for This Problem

• DFS Approach: DFS must traverse every single path to its leaf node to find the global minimum. If a tree has a very deep left subtree and a shallow right subtree, DFS will waste time exploring the deep left subtree first.
• BFS Approach: Since BFS traverses level by level, the first leaf node we encounter is guaranteed to be at the shallowest depth. We can terminate the algorithm immediately, saving significant computation time.

      3
     / \
    9  20
      /  \
     15   7

BFS Traversal:
Level 1: Node 3 (Not a leaf)
Level 2: Node 9 (Leaf node detected! Return depth = 2 immediately)

Java Implementation

import java.util.*;

public class MinimumDepth {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int depth = 1;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                
                // Check if we have reached a leaf node
                if (node.left == null && node.right == null) {
                    return depth;
                }
                
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            // Increment depth as we move to the next level
            depth++;
        }
        
        return depth;
    }
}

7. Problem 4: Maximum Level Sum of a Binary Tree

Problem Statement

Given the root of a binary tree, return the level (1-indexed) that has the maximum sum of node values. If there is a tie, return the smallest level.

Implementation Strategy

1. Maintain a maxSum variable initialized to Integer.MIN_VALUE and a maxLevel variable initialized to 1.
2. Maintain a level counter initialized to 1.
3. For each level, compute the sum of its nodes (levelSum).
4. After completing the level's traversal, compare levelSum with maxSum. If levelSum > maxSum, update maxSum and set maxLevel = level.
5. Increment level and repeat until the queue is empty.

Java Implementation

import java.util.*;

public class MaxLevelSum {
    public int maxLevelSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        int maxLevel = 1;
        int maxSum = Integer.MIN_VALUE;
        int level = 1;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            int levelSum = 0;
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                levelSum += node.val;
                
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            
            // CRITICAL: Check and update the maximum sum after calculating the entire level sum
            if (levelSum > maxSum) {
                maxSum = levelSum;
                maxLevel = level;
            }
            
            level++;
        }
        
        return maxLevel;
    }
}

8. Common Pitfalls & Debugging Workflows

When implementing BFS in coding interviews, candidates often make two common mistakes.

Pitfall 1: Forgetting to Enqueue Child Nodes

It is easy to focus on processing the current node's value and forget to add its children back into the queue. This causes the traversal to terminate prematurely.

• Incorrect Code:
  JAVA

  Copy

  TreeNode node = queue.poll();
  levelSum += node.val;
  // Missing node.left and node.right checks!
  

• Debugging Strategy: If your BFS only prints the root node and terminates, check if you wrote the conditional checks to enqueue node.left and node.right.

Pitfall 2: Placing Level-Wide Logic Inside the Inner Loop

In problems like Maximum Level Sum, the comparison logic must occur only after the entire level has been processed. Placing this check inside the inner for loop leads to incorrect results because it compares partial sums.

• Incorrect Code:
  JAVA

  Copy

  for (int i = 0; i < size; i++) {
      TreeNode node = queue.poll();
      levelSum += node.val;
      
      // BUG: Comparing before all nodes of the level are summed
      if (levelSum > maxSum) { 
          maxSum = levelSum;
          maxLevel = level;
      }
  }
  

• Correct Code:
  JAVA

  Copy

  for (int i = 0; i < size; i++) {
      TreeNode node = queue.poll();
      levelSum += node.val;
      // ... enqueue children ...
  }
  // CORRECT: Compare only after the loop completes
  if (levelSum > maxSum) {
      maxSum = levelSum;
      maxLevel = level;
  }
  

9. Tabular Synthesis of BFS Patterns

10. Summary and Key Takeaways

• Level-by-Level Traversal: BFS is the optimal choice when a problem requires processing nodes level by level or finding the shortest path in an unweighted tree or graph.
• Queue Data Structure: BFS relies on a Queue (FIFO) to manage the order of node exploration.
• The Size Snapshot Pattern: Capturing the queue size (queue.size()) before starting the level loop is essential to isolate and process only the nodes belonging to the current level.
• Early Termination Advantage: For shortest-path or minimum-depth problems, BFS can terminate the moment the target condition is met, making it much more efficient than DFS.
• Space Complexity Trade-off: The space complexity of BFS is $O(W)$, where $W$ is the maximum width of the tree. In a fully balanced tree, this can reach $O(N)$ due to the leaf nodes stored in the queue.
• Directional Control: You can easily reverse the output order of a level by using a double-ended queue structure (like LinkedList in Java) and toggling between addFirst() and addLast().
• Post-Loop Evaluations: Always perform level-wide comparisons (such as finding the maximum level sum) outside the inner level-processing loop to ensure you are working with complete level data.