Breadth-First Search (BFS): Level-Order Tree and Graph Traversal Explained with Examples

Breadth-First Search (BFS) is one of the most fundamental graph and tree traversal algorithms in computer science. It is widely used in scenarios where finding the shortest path or exploring levels of a structure systematically is crucial. From networking to pathfinding in games, BFS is often the go-to algorithm.

In this article, we will cover everything about BFS — starting from its definition, step-by-step working, implementation examples in Python, and visual diagrams that will help you deeply understand how BFS works for trees and for graphs.

Table of Contents

What Is Breadth-First Search (BFS)?

Breadth-First Search is a traversal algorithm that explores nodes level by level. If applied to a tree, it starts from the root node and explores all nodes at depth d before moving to depth d+1. In the case of graphs, BFS starts from a chosen source node and visits all immediate neighbors before moving outwards.

In essence, BFS uses a queue data structure (FIFO) to keep track of nodes to visit next. This makes BFS particularly good for discovering the shortest path in an unweighted graph.

How BFS Works Step-by-Step

Start from the root (or source node).
Visit the node and mark it as explored.
Push all its unvisited neighbors into a queue.
Dequeue a node from the front and repeat the process.
Continue until the queue is empty.

BFS on Trees: Level-Order Traversal

In binary trees, BFS is often referred to as level-order traversal. Let’s illustrate with an example.

Level Order Traversal of this tree would be: 1 → 2 → 3 → 4 → 5 → 6 → 7. Notice how BFS explores nodes level by level.

Python Example: BFS in a Binary Tree


from collections import deque

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def bfs_level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        result.append(node.value)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
            
    return result

# Example Tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

print("Level Order Traversal:", bfs_level_order(root))

Output:

Level Order Traversal: [1, 2, 3, 4, 5, 6, 7]

BFS on Graphs

When applied to graphs, BFS is slightly more complex than tree traversal because we need to handle cycles and disconnected components. To prevent infinite loops, we maintain a visited set.

Starting BFS traversal from node 1 produces: 1 → 2 → 3 → 4 → 5 → 6 → 7.

Python Example: BFS in Graph


from collections import deque

def bfs_graph(graph, start):
    visited = set()
    queue = deque([start])
    result = []
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            result.append(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
    return result

# Graph represented as adjacency list
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6, 7],
    4: [],
    5: [],
    6: [],
    7: []
}

print("BFS Traversal:", bfs_graph(graph, 1))

Output:

BFS Traversal: [1, 2, 3, 4, 5, 6, 7]

Applications of BFS

Shortest Path in Unweighted Graphs: BFS guarantees shortest path discovery in terms of edge count.
Social Networks: Finding connections or degrees of separation between people.
Web Crawlers: Exploring web pages layer by layer.
AI and Games: Finding the shortest way out of a maze.
Network Broadcasting: Simulating message propagation level by level.

Time and Space Complexity

Time Complexity: O(V + E) for graphs, where V = vertices, E = edges.
Space Complexity: O(V) for maintaining visited sets and queues.

Interactive BFS Visualization

If you want to deeply understand BFS, try simulating the queue-based expansion. Here’s a small interactive Python snippet (can be adapted for Jupyter/Colab) where you can enter your own graph and source node:


# Interactive BFS Simulation
from collections import deque

def interactive_bfs():
    n = int(input("Enter number of nodes: "))
    graph = {}
    for i in range(n):
        node = input(f"Enter node {i+1} name: ")
        neighbors = input(f"Enter neighbors of {node} (comma separated): ").split(",")
        graph[node] = [nbr.strip() for nbr in neighbors if nbr.strip()]
    
    start = input("Enter starting node: ")
    print("BFS Traversal:", bfs_graph(graph, start))

# Run and input your own graph interactively
# interactive_bfs()

Conclusion

Breadth-First Search (BFS) is not just an algorithm but a doorway to solving many real-world computational challenges. Whether you’re traversing a tree, simulating a social network connection, or finding the shortest path on a map, BFS provides a highly intuitive yet powerful approach. By mastering BFS, you build a strong foundation for exploring more advanced algorithms like Dijkstra’s and A*.

With its simplicity, guaranteed shortest path in unweighted graphs, and wide range of applications, BFS remains one of the core techniques every programmer should have in their toolkit.