# Coding Patterns: Breadth First Search (BFS)

In **Coding Patterns** series, we will try to *recognize* common patterns *underlying* behind each algorithm question, using real examples from Leetcode.

Previous posts were about Sliding Window, Two Pointers, Fast & Slow Pointers, Merge Intervals, Cyclic Sort and In-place Reversal of a Linked List patterns and today, we will introduce Breadth First Search (BFS) pattern which is very useful to solve the problems involving traversal of a tree in a **level-by-level order**.

We will use a Queue to keep track of all the nodes of a level before we jump onto the next level. This also means that the space complexity of the algorithm will be **O(N)**, where **N** is the *maximum number of nodes* on any level.

## Problem: Binary Tree Level Order Traversal

**LeetCode 102 - Binary Tree Level Order Traversal** [*medium*]

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

**For example:**

Given binary tree: `[3, 9, 20, null, null, 15, 7]`

```
3
/ \
9 20
/ \
15 7
```

return its level order traversal as:

```
[
[3],
[9,20],
[15,7]
]
```

### Breadth First Search Solution

Since we need to traverse all nodes of each level before moving onto the next level, we can use the Breadth First Search (BFS) technique to solve this problem.

We can use a Queue to efficiently traverse in BFS fashion. Here are the steps of our algorithm:

- Start by pushing the
`root`

node to the queue. - Keep iterating until the queue is empty.
- In each iteration, first count the elements in the queue (let’s call it
`level_size`

). We will have these many nodes in the current level. - Next, remove
`level_size`

nodes from the queue and push their`value`

in an array to represent the current level. - After removing each node from the queue, insert both of its children into the queue.
- If the queue is not empty, repeat from step
**3**for the next level.

```
from collections import deque
from typing import List
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
result = []
if root is None:
return result
queue = deque()
queue.append(root)
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
current_node = queue.popleft()
current_level.append(current_node.val) # add node to current level
if current_node.left:
queue.append(current_node.left)
if current_node.right:
queue.append(current_node.right)
result.append(current_level)
return result
```

**Time Complexity**: **O(N)** where ** N** is the total number of nodes in the tree.

**Space Complexity**: **O(N)**, since we need an **O(N)** space to return the result. We will also need **O(N)** for the queue.

## How to identify?

This approach is quite useful when dealing with the problems involving traversal of a tree in a **level-by-level order**.

When the problem asks the traversal of a tree, you should think about Breadth First Search (BFS) pattern and using it in combination with the Queue structure.

## Similar LeetCode Problems

- LeetCode 103 - Binary Tree Zigzag Level Order Traversal [
*medium*] - LeetCode 104 - Maximum Depth of Binary Tree [
*easy*] - LeetCode 107 - Binary Tree Level Order Traversal II [
*easy*] - LeetCode 111 - Minimum Depth of Binary Tree [
*easy*] - LeetCode 637 - Average of Levels in Binary Tree [
*easy*] - LeetCode 994 - Rotting Oranges [
*easy*] - LeetCode 1197 - Minimum Knight Moves [
*medium*] [*premium*]