liveBook · Manning

Breadth-first search

As explained in Algorithms Every Programmer Should Know

Breadth-first search is a graph or tree traversal algorithm that explores vertices level by level from a starting vertex.

Breadth-first search (BFS) explores a tree layer by layer: it checks a node’s immediate children before moving on to their children. A FIFO queue keeps track of which nodes to visit next. section 1.4.4 section 1.4.3

Search a tree from node 5

To find node 8, first check node 5, then check all of its children. Only after checking that whole layer do you move down and search the next. Unlike depth-first search, BFS does not follow one path down to a leaf before exploring other branches. section 1.4.4

For graphs, track visited vertices to avoid revisiting nodes in cycles. The summary gives BFS a time cost of O(V + E); for trees, it gives O(V) time and O(W) space, where W is the tree’s width. section 1.5 section 1.5

Figure 1.9 The two fundamental strategies for searching non-linear data structures. Left: Depth-First Search (DFS) goes deep down a single path to a leaf node. Right: Breadt-First Search (BFS) expands outward, exploring all the neighboring nodes layer by layer before descending to the next level.

Compare the diagrams to see BFS expand across a layer while DFS follows a path downward. section 1.4.4

Listing 1.5 Code implementation of a tree
 
from collections import deque
 
class TreeNode:
    def __init__(self, value): #A
        self.value = value
        self.left = None
        self.right = None
 
def tree_bfs(root):
    """
    Executes a Breadth-First Search traversal on a Binary Tree.
    Outputs the node values layer-by-layer (level-order).
    """
    if not root:
        return []
         
    queue = deque([root]) #B
    traversal_output = []
    
    while queue:
      
        current_node = queue.popleft() #C
        traversal_output.append(current_node.value)
        
        if current_node.left:
            queue.append(current_node.left) #D
            
        if current_node.right:
            queue.append(current_node.right) #E
            
    return traversal_output
 
def tree_dfs(root):
    """
    Executes an iterative Depth-First Search traversal on a Binary Tree.
    Outputs the node values along vertical paths before moving laterally.
    """
    if not root:
        return []
        
    stack = [root] #F
    traversal_output = []
    
    while stack:
        current_node = stack.pop() #G
        traversal_output.append(current_node.value)
        
        if current_node.right:
            stack.append(current_node.right) #H
        if current_node.left:
            stack.append(current_node.left)
            
    return traversal_output

See a Python implementation that uses a queue to return binary-tree node values in level order. section 1.4.4

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains queue-based traversal and complexity, with a Python tree implementation; does not detail a graph implementation.
Examples
Traces a search from root node 5 to node 8 and includes a level-order binary-tree implementation.
What it assumes
Builds on FIFO queues and introduces them as a traversal aid.
What you can do after
Apply BFS to traverse a binary tree in level order using a FIFO queue.
How it connects
Connects BFS with queues, trees, graphs, and depth-first search.

Also explained in

Compare how 10 books explain breadth-first search →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.