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; }; 

Answer 1

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]);     }   } };