breadth-first traversal of a tree in javascript

Question

I am trying to learn data structures well and implemented the following code for a depth-first traversal/application of a callback on a regular tree:

Tree.prototype.traverse = function (callback) {
  callback(this.value);

  if (!this.children) {
    return;
  }
  for (var i = 0; i < this.children.length; i++) {
    var child = this.children[i];
    child.traverse(callback);
  }
};

How could I change this to make it breadth first instead? This is what the Tree Class looks like:

var Tree = function (value) {
  var newTree = {};

  newTree.value = value;
  newTree.children = [];
  extend(newTree, treeMethods);

  return newTree;
};

Matt Timmermans · Accepted Answer · 2017-02-28T05:11:20.060

61

Fundamentally, the difference between DFS and BFS is that with a DFS you push the children of the current node onto a stack, so they will be popped and processed before everything else, while for BFS you push the children onto the end of a queue, so they will be popped and processed after everything else.

DFS is easy to implement recursively because you can use the call stack as the stack. You can't do that with BFS, because you need a queue. Just to make the similarity clear, lets convert your DFS to an iterative implementation first:

//DFS
Tree.prototype.traverse = function (callback) {
  var stack=[this];
  var n;

  while(stack.length>0) {

    n = stack.pop();
    callback(n.value);

    if (!n.children) {
      continue;
    }

    for (var i = n.children.length-1; i>=0; i--) {
       stack.push(n.children[i]);
    }
  }
};

And now BFS

//BFS
Tree.prototype.traverse = function (callback) {
  var queue=[this];
  var n;

  while(queue.length>0) {

    n = queue.shift();
    callback(n.value);

    if (!n.children) {
      continue;
    }

    for (var i = 0; i< n.children.length; i++) {
       queue.push(n.children[i]);
    }
  }
};

edited Feb 28 '17 at 05:11

answered Nov 14 '15 at 03:07

Matt Timmermans

53,709
3
46
87

You can replace the for with `stack = stack.concat(n.children)` – Andras Szell Nov 23 '17 at 17:44
3

@AndrasSzell that would change the complexity of the algorithm from O( |V| + |E| ) to O( |V|^2 + |E| ), since concat() allocates a new array. – Matt Timmermans Nov 23 '17 at 18:01
Array in JS is basically a hashtable, so there's no difference in complexity between concat and push. – Andras Szell Nov 23 '17 at 18:41
10

No, an array is not implemented like a hash table. You can use it like a hash, but JS implementations typically optimize arrays for array-like access. HOWEVER... it makes no difference to the above -- allocating a new hash table would also change the complexity similarly, and the difference between concat and push is that concat allocates a whole new one, while push does not. – Matt Timmermans Nov 23 '17 at 18:58
why in the first script you push the children in order, while in the second script you push the children in reverse order? That doesn't change almost anything – Totty.js Oct 31 '18 at 05:16
1

@Totty.js That's so I visit the children in the order I discovered them. In DFS we pop from the end of the stack, so I want to first child at the end. In BFS we pop from the front of the queue so I want the first child at the front. It's not super important, but it's nice – Matt Timmermans Oct 31 '18 at 16:13
Another option for the DFS for loop() using ES 6+ standards is: `n.children.slice(0).reverse().map((x) => { stack.push(x) });` (which adds the children to the stack in reverse order) – Sterling Bourne Mar 04 '19 at 17:16
Note necessarily a recommendation or making any comment about time complexity, but certainly for lexical simplicity and cognitive simplicity, it should be noted that `push` takes a variable number of arguments as a rest parameter, so pushing an array of items into an array can be achieved with the spread operator. I would like to think the ES implementation can optimise this. `queue.push(…n.children);` – barry_j_northern Feb 22 '23 at 07:58

breadth-first traversal of a tree in javascript

1 Answers1

Linked