Back to: Python Data Structure and Algorithims

🌳 Implementing Breadth-First Search (BFS) in a Binary Search Tree

In this post, we’ll dive into how to code Breadth-First Search (BFS) for a Binary Search Tree (BST).

We’ve already learned the concept of BFS — visiting nodes level by level from top to bottom — and now it’s time to implement it in code!

🧠 Quick Recap: What Is BFS?

In Breadth-First Search, we explore the tree level by level, starting from the root.
That means we visit:

The root node first,
Then all its children (second level),
Then all their children (third level), and so on.

For example, given this binary tree:

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

The BFS traversal order will be:

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

🏗️ Building the BFS Method

We’ll write the BFS method inside the Binary Search Tree class.
That’s why we’ll use the self keyword — it refers to the current instance of the tree.

Here’s how we’ll build it step-by-step.

🪜 Step 1: Set Up Initial Variables

First, we define our method:

def BFS(self):

Inside this method, we’ll create three key variables:

current_node → Starts at the root of the tree
```
current_node = self.root
```
queue → A list used to track which nodes to visit next
```
queue = []
```
results → Stores the final BFS traversal values
```
results = []
```

💡 Note:
Technically, a list is not the most efficient structure for a queue (because removing from the front is O(n)),
but we’ll use it here for simplicity since lists are familiar and easy to visualize.

🪜 Step 2: Add the Root Node to the Queue

Before starting the traversal loop, we need to put the root node into the queue:

queue.append(current_node)

This is an important step — if we skip this, the queue starts empty, and our loop won’t run at all!

At this point:

Queue: [47]
Results: []

🪜 Step 3: Build the While Loop

We’ll use a while loop that runs as long as there are nodes in the queue:

while len(queue) > 0:

Inside the loop, we’ll:

Dequeue (pop) the first node
```
current_node = queue.pop(0)
```
Store its value in results
```
results.append(current_node.value)
```

Add its left and right children (if any) to the queue

if current_node.left is not None:
    queue.append(current_node.left)
if current_node.right is not None:
    queue.append(current_node.right)

This process continues until the queue is empty — meaning we’ve visited every node.

🧩 Step 4: The Complete BFS Method

Now, combining all the parts together, here’s the full BFS method inside the BinarySearchTree class:

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        # ... (Insertion logic here)
        pass

    def BFS(self):
        current_node = self.root
        queue = []
        results = []

        if current_node is None:
            return results

        queue.append(current_node)

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

            if current_node.left is not None:
                queue.append(current_node.left)
            if current_node.right is not None:
                queue.append(current_node.right)

        return results

🧠 Step 5: Visualize the Execution

Let’s imagine how this runs with our earlier tree:

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

Step	Queue Before	Current Node	Queue After	Results
1	[47]	47	[21, 76]	[47]
2	[21, 76]	21	[76, 18, 27]	[47, 21]
3	[76, 18, 27]	76	[18, 27, 52, 82]	[47, 21, 76]
4	[18, 27, 52, 82]	18	[27, 52, 82]	[47, 21, 76, 18]
5	[27, 52, 82]	27	[52, 82]	[47, 21, 76, 18, 27]
6	[52, 82]	52	[82]	[47, 21, 76, 18, 27, 52]
7	[82]	82	[]	[47, 21, 76, 18, 27, 52, 82]

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

🧪 Step 6: Testing the BFS Method

# Create the tree
my_tree = BinarySearchTree()
my_tree.insert(47)
my_tree.insert(21)
my_tree.insert(76)
my_tree.insert(18)
my_tree.insert(27)
my_tree.insert(52)
my_tree.insert(82)

# Perform BFS
print(my_tree.BFS())

Output:

[47, 21, 76, 18, 27, 52, 82]

And notice — the returned list perfectly matches the order in which the tree was built!

✨ Key Takeaways

BFS traverses the tree level by level.
The method uses a queue to store nodes temporarily while exploring.
The results list stores only the node values — not the full node objects.
Once the queue becomes empty, traversal is complete.
The output of BFS visually mirrors the structure of the tree itself.