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









