Breadthfirst search (BFS) is an algorithm used to traverse or search through a tree or graph data structure. It explores all the nodes at the present depth prior to moving on to the nodes at the next depth level. In contrast to depthfirst search which goes deep down a single branch before exploring other branches, BFS traverses the tree levelbylevel from top to bottom and from left to right.
BFS has various applications in graphs and trees such as finding the shortest path between two nodes, solving maze puzzles, web crawling, peertopeer networks, and more. When applied to a binary tree, BFS can be used to traverse the tree in a levelorder manner and calculate the minimum distance between the root node and any other node.
In this comprehensive guide, we will cover the following topics related to implementing a BFS algorithm to traverse a binary tree in Python:
Table of Contents
Open Table of Contents
 Overview of BreadthFirst Search on Binary Trees
 BFS Algorithm Logic and Pseudocode
 Time and Space Complexity Analysis
 Binary Tree Data Structure in Python
 Implementing BFS Algorithm to Traverse Binary Tree
 BFS vs DFS Comparison
 Example Python Code for BFS Binary Tree Traversal
 Applications of BFS on Binary Trees
 Summary and Key Takeaways
Overview of BreadthFirst Search on Binary Trees
Breadthfirst search (BFS) is a tree/graph traversal algorithm that explores nodes levelbylevel starting from the root node and moving down to the leaf nodes. The key characteristic of BFS is that it visits all the nodes at a given level before proceeding to the nodes at the next level.
Some key properties of BFS algorithm are:
 Starts traversing from a selected root node and explores all the neighboring nodes.
 Uses a queue (FIFO) to maintain the list of nodes that need to be traversed.
 Traverses the breadth or width of the tree first before going to the next depth level.
In terms of binary trees, BFS explores the tree horizontally level by level. The traversal order follows:
 Visit the root node first.
 Move to the left subtree and traverse all nodes.
 Finally, move to the right subtree and traverse all nodes.
The nodes on each level are visited from left to right. Below is a sample BFS traversal order on a binary tree:
A
/ \
B C
/ \ \
D E F
BFS Order: A B C D E F
Some applications of breadthfirst search for binary trees include:
 Finding the minimum depth of a binary tree.
 Printing the levelorder traversal of nodes.
 Calculating the sum or average of each depth level.
 Finding the level of a given node value.
 Determining the minimum distance between two nodes.
 Serializing and deserializing a binary tree.
Now let’s look at the algorithm logic and pseudocode for BFS on binary trees.
BFS Algorithm Logic and Pseudocode
The breadthfirst search algorithm relies on a queue data structure to traverse a tree in a levelorder manner. Here are the logical steps involved:

Start by inserting the root node into a queue.

Create a loop that will run as long as there are nodes still left in the queue.

For each iteration:
a. Dequeue the front node from the queue.
b. Process the node, e.g. print its value.
c. Check if the dequeued node has a left child, if yes enqueue the left child node.
d. Check if the dequeued node has a right child, if yes enqueue the right child node.

Repeat steps 2 and 3 until the queue is empty.
The above logical steps can be converted into the following BFS pseudocode for binary trees:
BFS(rootNode):
//create empty queue
queue = []
//mark rootNode as visited and enqueue
queue.enqueue(rootNode)
while queue is not empty:
//dequeue front node from queue
currentNode = queue.dequeue()
//process current node
Process(currentNode)
//check if left child exists, enqueue if so
if currentNode.leftChild exists:
queue.enqueue(currentNode.leftChild)
//check if right child exists, enqueue if so
if currentNode.rightChild exists:
queue.enqueue(currentNode.rightChild)
end while
end BFS
This covers the key logic behind implementing BFS traversal on binary trees. Next, we’ll analyze the time and space complexity.
Time and Space Complexity Analysis
The time complexity of the BFS algorithm on a binary tree is O(N), where N is the total number of nodes in the binary tree. This is because BFS traverses through each node eventually.
In the worst case scenario, when the tree is a complete binary tree, the traversal will have to traverse all levels of the tree, therefore the worst case time complexity is O(N).
The space complexity for BFS on a binary tree is O(W), where W is the maximum width or number of nodes at any level. This space is occupied by the queue to store nodes of a single level.
In the worst case, the space complexity can be O(N) when the binary tree is skewed and has a maximum width of N/2 nodes.
Now that we have covered the basics of BFS, let’s explore the data structure concepts relevant to binary trees in Python.
Binary Tree Data Structure in Python
Before we can implement BFS on binary trees in Python, we need to understand how binary trees are represented in Python through different data structures.
A binary tree is defined as a tree data structure where each node has at most two children termed left child and right child. Some key properties of binary trees are:
 Each node has up to two children nodes referred to as left and right child.
 The left subtree of a node contains nodes with keys lesser than the node’s key.
 The right subtree of a node contains nodes with keys greater than the node’s key.
 Binary trees with N nodes will have N1 edges.
There are different types of binary trees:
Full Binary Tree  Every node has 0 or 2 children. All leaf nodes are at 2 levels.
Complete Binary Tree  All levels except the last have maximum nodes. The last level has all nodes to the left side.
Perfect Binary Tree  All internal nodes have 2 children and all leaf nodes are at the same level. Perfect trees are complete by definition.
In Python, a binary tree can be represented in various ways:
Using a Node Class
We can create a Node class which stores a value and pointers to the left and right child nodes:
class Node:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
Linked Structure
Each node stores reference to child nodes forming a linked structure:
A
/ \
B C
/ \ / \
D E F G
List of Lists
A list of lists can represent a binary tree level by level:
binary_tree = [[1], [2,3], [4,5,6]]
Dictionary
We can also store child nodes in a dictionary format:
binary_tree = {
'value': 1,
'left': {
'value': 2,
'left': {
'value': 4
},
'right': {
'value': 5
}
},
'right': {
'value': 3,
'left': {
'value': 6
}
}
}
These are some common ways to represent binary trees in Python before implementing BFS.
Implementing BFS Algorithm to Traverse Binary Tree
Now we are ready to implement the breadfirst search algorithm to traverse a binary tree in Python.
The key steps for BFS implementation are:
Initialize Data Structures
We need a visited set to track visited nodes and prevent repeating nodes. This can be a Python set or dictionary.
We also need a queue (FIFO) to store nodes of each level while traversing. This can be a normal queue or deque object.
visited = set() # Set to track visited nodes
queue = deque() # Initialize queue
Start by Enqueuing Root Node
We start BFS by visiting the root node and enqueue it to the queue.
root_node = get_root() # Get root reference
queue.append(root_node)
visited.add(root_node)
Loop While Queue is Not Empty
We process each node in the queue sequentially by:
 Dequeuing the node
 Checking if left and right children exist
 Enqueue nonvisited children
 Process current node as needed
while queue:
current = queue.popleft() #dequeue front
# process current node
print(current.value)
if current.left and current.left not in visited:
queue.append(current.left)
visited.add(current.left)
if current.right and current.right not in visited:
queue.append(current.right)
visited.add(current.right)
We continue this iterative dequeuing, enqueueing and processing until the queue is empty.
BFS vs DFS Comparison
Breadthfirst search (BFS) has some differences compared to depthfirst search (DFS) when traversing binary trees:
Traversal Order
 BFS processes nodes levelbylevel in horizontal order.
 DFS processes nodes vertically down each branch from root to leaves.
Use Cases
 BFS is preferred for finding shortest path and calculating level of nodes.
 DFS is preferred for topological sorting and pathfinding.
Time Complexity
 Both are O(N) for traversing all nodes of a binary tree.
Space Complexity
 BFS requires O(W) space for queue to store a level’s nodes.
 DFS requires O(H) space to store recursion stack, where H is tree height.
Queue vs Stack
 BFS uses a queue data structure to store nodes levelwise.
 DFS uses a stack data structure to push nodes on recursion call stack.
To summarize, BFS vs DFS have tradeoffs to consider based on the problem we are solving. BFS gives horizontal levelorder traversal while DFS gives vertical topdown traversal.
Example Python Code for BFS Binary Tree Traversal
Here is example Python code implementing BFS traversal on a sample binary tree:
from collections import deque
# Binary tree node class
class Node:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# BFS function to traverse binary tree
def traverseBFS(root):
if not root:
return
queue = deque()
queue.append(root)
while queue:
current = queue.popleft()
print(current.val, end=' ')
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
# Construct sample binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
# Traverse tree BFS
print("BreadthFirst Traversal:")
traverseBFS(root)
Output:
BreadthFirst Traversal:
1 2 3 4 5
This performs a levelorder traversal by visiting nodes from left to right on each depth level. The queue helps maintain nodes levelwise in proper BFS order.
Applications of BFS on Binary Trees
Breadthfirst search traversal of binary trees has several realworld applications:
Finding Minimum Depth of Binary Tree
We can find the minimum depth by traversing levelbylevel and returning the level count once a leaf node is found.
Printing Level Order Traversal
BFS allows printing nodes levelbylevel in proper horizontal order.
Finding Level Averages and Sums
We can calculate sum or average of node values at each level while traversing the tree.
Level of Node
We can find the level of a target node by incrementing level counter in BFS until the target is reached.
Shortest Path Between Nodes
BFS can find the shortest path between two nodes by tracking parent pointers.
Serialize and Deserialize Binary Tree
We can construct a binary tree back from its level order traversal string generated using BFS.
PeertoPeer Networking
BFS helps model peertopeer network connections and data transfers levelwise.
These are some common applications of breadthfirst search when working with binary trees.
Summary and Key Takeaways
To summarize, here are the key points to remember when implementing breadthfirst search traversal on binary trees in Python:

BFS explores nodes levelbylevel starting from the root in horizontal order.

Maintain a queue to store nodes levelwise and track visited.

Use a loop to dequeuer front node, process node, enqueue children.

Compare BFS vs DFS based on order, space complexity, and use cases.

Code BFS using a queue and while loop to visit nodes horizontally.

Apply BFS to find minimum depth, level order printing, shortest path, etc.

Represent binary trees using linked nodes, lists, or dictionary structure.

Analyze time and space complexity tradeoffs for BFS algorithm.
Breadthfirst search provides an efficient way to traverse binary trees levelwise. Mastering BFS implementation in Python is key for treebased algorithms and interview questions.
Some recommendations for further exploration are studying applications of BFS on graph data structures, comparing additional tree traversal algorithms, and practicing BFS coding problems to improve mastery.