Data Structures and Algorithms: Breadth First Search

Introduction

In a breadth first search, we traverse a tree one level at a time, visiting each node on a level before visiting any potential children nodes. We will use a queue to explore this data structure. See part three of this series for further details on queues.

Breadth First Traversal

Considering the root of the tree, we add the root to the queue. We then remove the node at the front of the queue and print out its value. We also consider any children the node might have and then add them to the back of the queue, going from left to right. We repeat this process until the queue is empty. We can use the following binary tree to illustrate this.

In this example we start by adding the root to our queue.

[a]

We remove the node at the front of the queue, printing out its value. We then add any children that this node might have to the back of the queue.

[b, c]

We repeat the process, removing the node at the front of the queue and printing its value, and then we add any of its children to the back of the queue.

[c, d, e]

We continue the process until the queue is empty. The resulting breadth first traversal of our example tree will be: a, b, c, d, e, f, g.

A breadth first traversal can be achieved in javascript using the following code:

const breathFirstTraversal = (root) => {
  let queue = [root];

  while (queue.length > 0) {
    let currentNode = queue.shift();

    console.log(currentNode.val);

    if (currentNode.left !== null) {
      queue.push(currentNode.left);
    }
    if (currentNode.right !== null) {
      queue.push(currentNode.right);
    }
  }
};

Breadth First Search

Knowing how to implement a breadth first traversal, we can now proceed to implement a breadth first search in order to find a target value in a tree. Here is how this can be done in javascript:

const breathFirstSearch = (root, target) => {
  let queue = [root];

  while (queue.length > 0) {
    let currentNode = queue.shift();

    if (currentNode.val === target) {
      return true;
    }

    if (currentNode.left !== null) {
      queue.push(currentNode.left);
    }
    if (currentNode.right !== null) {
      queue.push(currentNode.right);
    }
  }

  return false;
};

A breadth first traversal can also be used to add up all of the node values in a tree.

Conclusion

This concludes the basics of a breadth first traversal and how this can be used as a basis for a breadth first search. As previously stated, the implicit data structure used in a breadth first traversal is a queue.