JavaScript Depth First Traversal

Posted on: July 20, 2017

Traversing a tree by going in one path as down as possible is possible recursively or with an iteration. Let's first create a node function that will hold the information of each node.

1var node = function (v, c) {
2  return { value: v, children: c };
3};
4
5var node5 = node("node5");
6var node4 = node("node4");
7var node3 = node("node3");
8var node2 = node("node2", [node5]);
9var node1 = node("node1", [node3, node4]);
10var graph = node("root", [node1, node2]);

The graph is simple, and is the same that we used in the breadth first approach. The algorithm to traverse the tree doesn't need any structure since we will call recursively every children when we find one. This has the advantage to not carry a stack with us, but the disadvantage that we may want to have additional variable to not go too deep in one direction.

1function depthFirstRecursive(node, callback) {
2  callback(node);
3  if (node.children) {
4    for (var i = 0; i < node.children.length; i++) {
5      var child = node.children[i];
6      if (!child.hasBeenVisited) {
7        depthFirstRecursive(child, callback);
8      }
9    }
10  }
11}
12
13depthFirstRecursive(graph, function (node) {
14  console.log(node.value);
15});

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

The iterative approach is similar. However, we loop from the length of the children array to zero. We do this if we want to have the exact same output of the recursive one. Without loop in reverse, we still do a depth first but from the right side of the tree first instead of the left side.

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

We are using unshift to push any new child at the beginning of the array (stack) and get the data from the beginning of the array to (it's a stack!).