## Fundamentals

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

#### 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.

#### 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.

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

#### 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.

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 verison 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.

## Complexity Analysis

The base complexity of BFS is:

**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).

Loading comments...