Breadth-First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph in breadth-first order, i.e., it visits all the vertices at the same level before moving to the next level. It is commonly used to solve problems involving graphs, trees, or other data structures that can be represented as graphs.
To illustrate how to use BFS, let's consider an example question:
Question: Given a binary tree, find the level with the maximum sum of the nodes and return that sum.
Example:
1 / \ 2 3 / \ / \ 4 5 6 7
In the above binary tree, the levels are numbered from top to bottom starting from 0. The maximum sum occurs at level 2, and the sum of the nodes at that level is 6 + 7 = 13. Therefore, the expected output for this example is 13.
Now, let's see how we can use the BFS pattern to solve this problem step by step:
Step 1: Define a queue and enqueue the root node of the binary tree.
Step 2: Initialize a variable maxSum
to keep track of the maximum sum encountered so far and set it to a minimum value (e.g., negative infinity).
Step 3: Initialize a variable currentLevel
to keep track of the current level number and set it to 0.
Step 4: Start a loop that continues until the queue is empty.
Step 5: Inside the loop, get the current size of the queue, size = queue.size()
. This will represent the number of nodes at the current level.
Step 6: Initialize a variable levelSum
to store the sum of nodes at the current level and set it to 0.
Step 7: Start another loop that iterates size
number of times.
Step 8: Inside the nested loop, dequeue a node from the queue and add its value to levelSum
.
Step 9: Enqueue the left and right child of the dequeued node if they exist.
Step 10: After the nested loop ends, check if levelSum
is greater than maxSum
. If so, update maxSum
with levelSum
.
Step 11: Increment currentLevel
by 1.
Step 12: Repeat from Step 5 until the queue is empty.
Step 13: Return maxSum
as the result.
Here's the Python code that implements the BFS pattern to solve the given question:
from collections import deque class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def max_level_sum(root): if not root: return 0 queue = deque() queue.append(root) maxSum = float('-inf') currentLevel = 0 while queue: size = len(queue) levelSum = 0 for _ in range(size): node = queue.popleft() levelSum += node.val if node.left: queue.append(node.left) if node.right: queue.append(node.right) if levelSum > maxSum: maxSum = levelSum currentLevel += 1 return maxSum
You can test the above code with the provided example tree:
# Creating the example tree root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) root.right.left = TreeNode(6) root.right.right = TreeNode(7) # Testing the max_level_sum function print(max_level_sum(root))
The output of the above code will be:
13
This is the expected output since the maximum sum of nodes occurs at level 2, and the sum of nodes at that level is 13.
In summary, we used the BFS pattern to traverse the binary tree level by level, keeping track of the sum of nodes at each level and updating the maximum sum encountered so far. By the end of the traversal, we returned the maximum sum as the result.
You can apply the BFS pattern to solve various problems involving graph or tree traversal. The key is to use a queue to keep track of the nodes to be processed and ensure that the algorithm visits all the nodes at the same level before moving to the next level.