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
}
Top comments (0)