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
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
Given binary tree: [3, 9, 20, null, null, 15, 7]
return its level order traversal as:
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
rootnode 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_sizenodes from the queue and push their
valuein 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.