Algorithms: Breadth First Search

Tree and Graph traversal is a popular topic in coding interviews. There are many approaches to graph traversal but one of the most common and important to be familiar with is Breadth First Search (BFS). We'll explore the basic ideas of the algorithm and a few example implementations.

The Basics

Breadth First Search is an algorithm used to traverse graph data structures. It is the order in which the nodes will be visited. As the name implies the traversal is conducted in a breadth first manner, meaning that starting from a certain node we will traverse every node of the current level before exploring additional nodes at deeper levels.

Tree Order Traversal

Starting from the root node (6), each level is explored from left to right before moving to the next level.

Implementations

BFS algorithms are usually implemented iteratively using a queue data structure. We start by adding the root node to the queue. Then we iterate through the queue, removing the node and adding its children to the queue. This allows us to explore the graph level by level.

Problem

Given a binary tree, return an array of sub-arrays that represents its level by level traversal.

class Node {
  constructor(val) {
    this.val = val
    this.left = null
    this.right = null
  }
}

Solution

const bfs = (root) => {
 const result = []
 const queue = [ root ]

 while (queue.length) {
   const level = []
   const qLength = queue.length
   for (let x = 0; x < qLength; x++) {
      const node = queue.shift()
      level.push(node.val)
      if (node.left !== null) queue.push(node.left)
      if (node.right !== null) queue.push(node.right)
   }
  result.push(level)
 }
 return result
}