Breadth-First Search
Breadth-First Search Fundamentals
Count: 10
BFS is a level-by-level traversal algorithm. It starts at the root node of the binary tree and visits all nodes at the current level before moving to the next level of the tree.
Visualization
Python
def bfs(root):if not root:return []result = []queue = deque([root])while queue:curr_node = queue.popleft()result.append(curr_node.val)if curr_node.left:queue.append(curr_node.left)if curr_node.right:queue.append(curr_node.right)return result
breadth-first search
0 / 15
BFS Procedure
BFS uses a queue to keep track of the nodes it needs to visit, and follows these steps:
- Start at the root node and add it to the queue.
- While the queue is not empty, remove the node at the front of the queue and visit it.
- Add the children of the node to the back queue.
- Repeat steps 2 and 3 until the queue is empty, which means you've processed all nodes in the tree.
Queues in Python
In Python, you can use the deque class from the collections module to create a queue.
The deque class provides an append method to add elements to the end of the queue and a popleft method to remove elements from the front of the queue, both of which run in O(1) time.
Implementation
Below is a basic implementation of BFS on a binary tree. The result list stores the nodes in the order in which they are visited.
Visualization
Python
def bfs(root):if not root:return []result = []queue = deque([root])while queue:curr_node = queue.popleft()result.append(curr_node.val)if curr_node.left:queue.append(curr_node.left)if curr_node.right:queue.append(curr_node.right)return result
breadth-first search
0 / 15
Summary
- BFS is a traversal algorithm that visits all nodes at a particular level before moving to the next level.
- BFS uses a queue to keep track of the nodes it needs to visit.
Processing Levels
The distinguishing feature of BFS is that it visits all nodes at a particular level before moving onto the nodes at the next level.
Compared to depth-first search, BFS makes it much easier to tell when we have finished processing all nodes at a particular level. This makes it a natural candidate for questions that ask something about the nodes at each level, which is shown below in the Level-Order Traversal algorithm.
DESCRIPTION
Given a binary tree, return the level-order traversal of its nodes' values. (i.e., from left to right, level by level).
Input
Output
[[4], [2, 7], [1, 3, 6, 9]]
We can extend our basic BFS algorithm to calculate the number of nodes at each level by adding a for-loop that iterates over the size of the queue at the beginning of each level.
- Each time the for-loop runs, we add the current node to the current_level list.
- When the for-loop finishes, we have finished processing all nodes at that level, and we can add the current_level list to the result list. We can reset the current_level list to an empty list to prepare for the next level.
Solution
Python
from collections import dequedef level_order(root):if not root:return []result = []queue = deque([root])while queue:# number of nodes at the current levellevel_size = len(queue)current_level = []for _ in range(level_size):curr = queue.popleft()current_level.append(curr.val)if curr.left:queue.append(curr.left)if curr.right:queue.append(curr.right)# IMPORTANT# we have finished processing all nodes at the current levelresult.append(current_level)return result
To help you visualize how this algorithm works, the diagram below shows the state of the queue after we have finished processing the 2nd level of the tree.
Notice that queue contains the nodes at the 3rd level of the tree, [1, 3, 6, 9]. When we enter the next iteration of the while loop, the for loop will run 4 times to process these nodes.
from collections import dequedef level_order(root):if not root:return []result = []queue = deque([root])while queue:# number of nodes at current levellevel_size = len(queue)current_level = []for _ in range(level_size):curr = queue.popleft()current_level.append(curr.val)if curr.left:queue.append(curr.left)if curr.right:queue.append(curr.right)# IMPORTANT# we have finished processing all# nodes at the current levelresult.append(current_level)return result
Using a for-loop to iterate over the nodes at each level is such a common pattern that it is the version of BFS on binary trees you need to know for interviews. The practice problems we will look at next all use this version of BFS.
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(N) where N is the number of nodes in the tree. We visit each node exactly once.
Space Complexity: O(N) where N is the number of nodes in the tree. The space complexity is determined by the size of the queue, which can grow up to N/2 in the worst case (the last level of a full binary tree).
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.