Breadth-First Search in Binary Trees: Level-Order Traversal with Python

Learn how to perform a level-order (BFS) traversal on a binary tree using Python’s collections.deque. This beginner-friendly guide shows you step-by-step code, intuition, and real examples, perfect for LeetCode prep!

Why Level-Order Traversal?

If Depth-First Search (DFS) is like diving deep down one path of a maze, Breadth-First Search (BFS) is like exploring each floor of a building one level at a time. In a binary tree, BFS lets us visit all nodes at depth 0 (the root), then depth 1 (its children), then depth 2, and so on.

Level-order traversal (BFS) is the go-to technique for:

• Finding the shortest path in unweighted graphs or trees.
• Printing a tree level by level (nice for debugging!).
• Solving problems like “Zigzag Level Order” or “Average of Levels” on LeetCode.

We’ll use Python’s collections.deque as our queue (fast appends/pops) and build a result list of lists, one sublist per level.

Also read about the Python Program to Find Maximum Depth of a Binary Tree.

Intuition & Approach

1. Start at the root.
2. Use a queue to hold nodes of the current level.
3. While the queue isn’t empty:
   • Note the current queue size (level_size), that’s how many nodes are on this level.
   • Dequeue each node, record its value.
   • Enqueue its children (left then right) for the next level.
   • After processing level_size nodes, you’ve finished one level—append the collected values to result.

This approach ensures we visit nodes in perfect left-to-right, level-by-level order.

Code Implementation

from collections import deque

def level_order_traversal(root):
    """
    Perform a BFS (level-order) traversal on a binary tree and
    return a list of levels, where each level is a list of node values.
    """
    result = []
    if not root:
        return result

    queue = deque([root])

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(current_level)

    return result

Code Explanation

• Initialize:
  • result = [] will hold our final list of levels.
  • If root is None, return [] immediately.
• Setup Queue:
  • queue = deque([root]) seeds the BFS with the root node.
• Main Loop:
  • While queue has nodes, note level_size = len(queue).
  • Create an empty current_level = [] to collect this level’s values.
• Process One Level:
  • Loop level_size times:
    1. node = queue.popleft() dequeues the next node.
    2. current_level.append(node.val) records its value.
    3. If node.left exists, queue.append(node.left).
    4. If node.right exists, queue.append(node.right).
• Save Level:
  • After the for-loop, current_level holds all values for one depth—append it to result.
• Continue:
  • The next iteration processes the next depth, until the queue is empty.

Dry Run (Example)

Given the tree:

      1
     / \
    2   3
   / \   \
  4   5   6

• Start: queue = [1]
• Level 0:
  • level_size = 1.
  • Dequeue 1 → current_level = [1].
  • Enqueue 2, 3.
  • Append [1] to result.
• Level 1:
  • queue = [2, 3], level_size = 2.
  • Dequeue 2 → [2], enqueue 4,5.
  • Dequeue 3 → [2,3], enqueue 6.
  • Append [2,3].
• Level 2:
  • queue = [4,5,6], level_size = 3.
  • Dequeue 4 → [4]. No children.
  • Dequeue 5 → [4,5]. No children.
  • Dequeue 6 → [4,5,6]. No children.
  • Append [4,5,6].
• Done: queue empty.

Final result: [[1], [2,3], [4,5,6]]

Time and Space Complexity

• Time Complexity:
  • We visit each of the N nodes exactly once → O(N).
• Space Complexity:
  • The queue may hold up to the entire width of the tree (worst case, N/2 nodes at the lowest level) → O(N).
  • The result list stores all values → O(N).

Conclusion

Level-order traversal via BFS is incredibly powerful for problems that need to process nodes by depth. Python’s deque keeps it elegant and efficient. Whether you’re printing a tree level by level, finding the shortest path, or prepping for LeetCode’s “Binary Tree Zigzag” question, mastering this pattern is a must-have in your toolkit.

For any changes to the document, kindly email at code@codeanddebug.in or contact us at +91-9712928220.