JavaScript Breadth First Traversal

Posted on: July 18, 2017

Traversing a tree is not a task you have to do often, but it's still a good exercise to practice moving around a tree. Breadth first traversal consist of navigating one level at a time, visiting each siblings before moving to children.

Breadth first requires the use of a queue for it's iterative and recursive approach. This is a big different from is opposite depth first traversal approach who use only a stack for the iterative and doesn't need to hold any values for its recursive algorithm.

Let's start with defining a structure that represent a node.

1var node = function (v, c) {
2  return { value: v, children: c };
3};

As you can see, each node has a value and a children collection. The name could be more significant, but let's put that aside and create a tree.

1var node5 = node("node5");
2var node4 = node("node4");
3var node3 = node("node3");
4var node2 = node("node2", [node5]);
5var node1 = node("node1", [node3, node4]);
6var graph = node("root", [node1, node2]);

The tree is simple. It has a single root element that has 2 childrens : node 1 and node 2. Node a has two children : node 3 and 4. If we move back to the root, the second children, node 2, has only a single child : node 5.

1function breadthFirstRecursive(queue, callback) {
2  if (queue.length === 0) {
3    return;
4  }
5  var node = queue.shift();
6  callback(node);
7  if (node.children) {
8    for (var i = 0; i < node.children.length; i++) {
9      var child = node.children[i];
10      if (!child.hasBeenVisited) {
11        child.hasBeenVisited = true;
12        queue.push(child);
13      }
14    }
15  }
16  breadthFirstRecursive(queue, callback);
17}

The algorithm starts by looking at the queue to be sure that we still have something to proceed. If that's the case, we take the first element from the left. This is important because children will be pushed in the queue and that we do not want to visit them until we are done with all siblings of the level. The last piece of code is the invocation where we put the root in the queue to be proceeded.

1var queue = [];
2queue.push(graph);
3breadthFirstRecursive(queue, function (node) {
4  console.log(node.value);
5});

This output : Root, Node1, Node2, Node3, Node4, Node5

The iterative approach is similar with the same output if we provide the same input.

1function breadthFirstIterative(root, callback) {
2  var queue = [];
3  queue.push(root);
4  while (queue.length > 0) {
5    var node = queue.shift();
6    callback(node);
7    if (node.children) {
8      for (var i = 0; i < node.children.length; i++) {
9        var child = node.children[i];
10        if (!child.discovered) {
11          child.discovered = true;
12          queue.push(child);
13        }
14      }
15    }
16  }
17}
18
19breadthFirstIterative(graph, function (node) {
20  console.log(node.value);
21});

The recursive call is replaced by a loop that will proceed the queue until that this one is empty.