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.
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
public List<Integer> bfs(TreeNode root) { if (root == null) { return new ArrayList<>(); } List<Integer> result = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode currNode = queue.poll(); result.add(currNode.val); if (currNode.left != null) { queue.offer(currNode.left); } if (currNode.right != null) { queue.offer(currNode.right); } } return result;}
func bfs(root *TreeNode) []int { if root == nil { return []int{} } result := []int{} queue := []*TreeNode{root} for len(queue) > 0 { currNode := queue[0] queue = queue[1:] result = append(result, currNode.Val) if currNode.Left != nil { queue = append(queue, currNode.Left) } if currNode.Right != nil { queue = append(queue, currNode.Right) } } return result}
function bfs(root: TreeNode | null): number[] { if (!root) { return []; } const result: number[] = []; const queue: TreeNode[] = [root]; while (queue.length > 0) { const currNode = queue.shift()!; result.push(currNode.val); if (currNode.left) { queue.push(currNode.left); } if (currNode.right) { queue.push(currNode.right); } } return result;}
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.
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.
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.
from collections import dequedef level_order(root): if not root: return [] result = [] queue = deque([root]) while queue: # number of nodes at the current level level_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 level result.append(current_level) return result
public List<List<Integer>> levelOrder(TreeNode root) { if (root == null) { return new ArrayList<>(); } List<List<Integer>> result = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { // number of nodes at the current level int levelSize = queue.size(); List<Integer> currentLevel = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode curr = queue.poll(); currentLevel.add(curr.val); if (curr.left != null) { queue.offer(curr.left); } if (curr.right != null) { queue.offer(curr.right); } } // IMPORTANT // we have finished processing all nodes at the current level result.add(currentLevel); } return result;}
func levelOrder(root *TreeNode) [][]int { if root == nil { return [][]int{} } var result [][]int queue := []*TreeNode{root} for len(queue) > 0 { // number of nodes at the current level levelSize := len(queue) var currentLevel []int for i := 0; i < levelSize; i++ { curr := queue[0] queue = queue[1:] currentLevel = append(currentLevel, curr.Val) if curr.Left != nil { queue = append(queue, curr.Left) } if curr.Right != nil { queue = append(queue, curr.Right) } } // IMPORTANT // we have finished processing all nodes at the current level result = append(result, currentLevel) } return result}
function levelOrder(root: TreeNode | null): number[][] { if (!root) { return []; } const result: number[][] = []; const queue: TreeNode[] = [root]; while (queue.length > 0) { // number of nodes at the current level const levelSize = queue.length; const currentLevel: number[] = []; for (let i = 0; i < levelSize; i++) { const curr = queue.shift()!; currentLevel.push(curr.val); if (curr.left) { queue.push(curr.left); } if (curr.right) { queue.push(curr.right); } } // IMPORTANT // we have finished processing all nodes at the current level result.push(currentLevel); } 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.
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.
