BFS of Tree: Implementation Steps for Breadth-First Search and Level Order Traversal

In the world of data structures, a tree is a very important non-linear structure. There are many methods to traverse a tree, among which Breadth-First Search (BFS) is a classic approach. As the name suggests, BFS visits nodes in a “breadth-first” manner—meaning it first visits all nodes closest to the root (nodes on the same level), then moves to the next level. This level-by-level traversal is also commonly referred to as “level-order traversal.”

Why Learn BFS?¶

In tree problems, many scenarios require processing nodes level by level. For example, calculating the height of a tree can be done by accumulating levels one by one with BFS; checking if a tree is a complete binary tree also requires level-order node existence checks; and even path problems like finding the shortest path from root to leaf can be efficiently solved with BFS. Mastering BFS helps you handle level-related tree problems more clearly.

Implementation Steps of BFS (Taking Binary Tree as an Example)¶

The core of BFS is using a “queue” (FIFO - First-In-First-Out) data structure to assist in traversal. The specific steps are as follows:

1. Initialize the Queue: First, enqueue the root node. If the tree is empty (root does not exist), terminate the traversal directly.
2. Process the Queue in a Loop: While the queue is not empty, perform the following operations:
   - Dequeue the front node (front element) and visit it (e.g., print the node value).
   - Enqueue its child nodes (usually in the order of “left child first, then right child”).
3. Termination Condition: When the queue is empty, all nodes have been visited, and the traversal ends.

Understanding the BFS Process with an Example¶

To make it intuitive, let’s simulate the BFS traversal process with a specific binary tree:

        1
       / \
      2   3
     / \
    4   5

Node values: Root is 1, left child 2, right child 3; Node 2 has left child 4 and right child 5; other nodes have no children.

Simulating the BFS Process:
- Initial State: The queue contains only the root node 1, i.e., [1].
- First Loop: Dequeue node 1, visit 1. Enqueue its children (left then right) 2 and 3. The queue becomes [2, 3].
- Second Loop: Dequeue node 2, visit 2. Enqueue its children 4 and 5. The queue becomes [3, 4, 5].
- Third Loop: Dequeue node 3, visit 3. 3 has no children, so the queue remains unchanged after enqueue operations, becoming [4, 5].
- Fourth Loop: Dequeue node 4, visit 4. 4 has no children, so the queue becomes [5].
- Fifth Loop: Dequeue node 5, visit 5. 5 has no children, so the queue becomes empty.

At this point, the traversal ends, and the visit order is: 1 → 2 → 3 → 4 → 5, which is the level-order result.

Key Points Summary¶

• Role of the Queue: The queue acts as BFS’s “navigator,” ensuring nodes of each level are processed in order. After dequeuing a node, its children must be enqueued to ensure the next level is processed sequentially.
• Child Enqueue Order: For binary trees, enqueue left children first, then right children; for other tree types (e.g., n-ary trees), enqueue children in their natural order.
• Time Complexity: Each node is enqueued and dequeued exactly once, so O(n) (where n is the total number of nodes).
• Space Complexity: In the worst case (e.g., the last level of a complete binary tree), the queue can store up to n/2 nodes, so O(n).

By implementing BFS with a queue, you can clearly traverse all nodes of a tree level by level. Mastering this method helps you efficiently solve level-related tree problems and lays the foundation for learning more complex algorithms later.