Back to: Python Data Structure and Algorithims

🌳 Breadth-First Search (BFS) in Trees Explained Step-by-Step

In this section, we’ll take a closer look at how Breadth-First Search (BFS) works in a tree — step by step.

BFS is one of the most fundamental traversal techniques in data structures and is often called Level Order Traversal, because it visits nodes level by level, from top to bottom and left to right.

🧠 Quick Recap: What Is BFS?

In BFS, we start from the root node and visit all nodes at the current depth before moving on to nodes at the next level.

For example, if we have this tree:

        47
       /  \
     21    76
    / \    / \
   18 27  52 82

Then the BFS traversal order will be:

👉 47 → 21 → 76 → 18 → 27 → 52 → 82

This is because we start at the top (47), then move to the second row (21 and 76), then the third row (18, 27, 52, 82).

⚙️ Step-by-Step BFS Process

To perform BFS, we’ll use two lists (or arrays in Python):

Queue (Q) – helps keep track of nodes we need to visit next.
Results – stores the final values of the nodes we’ve visited.

Let’s go through the process visually and conceptually.

🪜 Step 1: Initialize the Queue and Results

Start with the root node (47).
Place the entire node (not just its value) into the queue.
Keep results empty for now.

Queue: [47]
Results: []

💡 Important: We store the whole node (which includes its left and right children), not just the value.
This allows us to explore its children later.

🪜 Step 2: Visit the First Node in the Queue

Remove the first node (47) from the queue.
Take its value and add it to the results list.

Queue: []
Results: [47]

Now, we’ll look at 47’s left and right children:

Left: 21
Right: 76

We add both entire nodes to the queue:

Queue: [21, 76]
Results: [47]

🪜 Step 3: Process the Next Node (21)

Remove 21 from the queue.
Move its value to results.
Add its children (18 and 27) to the queue.

Queue: [76, 18, 27]
Results: [47, 21]

🪜 Step 4: Process the Next Node (76)

Remove 76 from the queue.
Move its value to results.
Add its children (52 and 82) to the queue.

Queue: [18, 27, 52, 82]
Results: [47, 21, 76]

🪜 Step 5: Process the Remaining Nodes

Now we move through the remaining nodes in the queue one by one:

Current Node	Left Child	Right Child	Queue After Adding	Results After Adding
18	None	None	[27, 52, 82]	[47, 21, 76, 18]
27	None	None	[52, 82]	[47, 21, 76, 18, 27]
52	None	None	[82]	[47, 21, 76, 18, 27, 52]
82	None	None	[]	[47, 21, 76, 18, 27, 52, 82]

Once the queue becomes empty, it means we have visited all the nodes.

✅ Final Results List: [47, 21, 76, 18, 27, 52, 82]

🌈 Observing the Pattern

If we arrange the numbers in the results list level by level:

47
21 76
18 27 52 82

You’ll notice something amazing — it perfectly replicates the structure of the tree!
That’s why BFS is such a powerful and intuitive traversal technique — it mirrors how the tree looks level-wise.

🧩 Python-Like Pseudocode for BFS

Here’s a simple pseudocode that reflects our step-by-step logic:

def breadth_first_search(root):
    queue = []
    results = []

    if root is None:
        return results

    queue.append(root)

    while queue:
        current_node = queue.pop(0)
        results.append(current_node.value)

        if current_node.left:
            queue.append(current_node.left)
        if current_node.right:
            queue.append(current_node.right)

    return results

💡 Key Takeaways

BFS uses a queue to keep track of nodes level by level.
It’s perfect for exploring the tree in a top-down, left-to-right manner.
When visualized, the traversal order reflects the exact structure of the tree.
BFS is widely used in shortest path algorithms, network traversal, and AI search problems.