How to collect all nodes of a Tree structure, grouped by depth level?

Question

I have a classic Tree-structure with childs and parent node. Now, i would like to collect all nodes grouped by depth starting from the lowest level (i.e. in reverse order), like this:

nodes[
  ["A4"],
  ["A3","B3"],
  ["A2","B2","C2"],
  ["A1","B1","C1"],
  ["ROOT"]
];

While getting the depth level by using the recursive traversal approach is very easy, i'm wonder if there is any method to get immediately the depth level during the Tree traversal in a BFS or DFS search.

I'am aware that i could store the depth level during the node insertion, but as i'm doing a lot of insertion and removals, i would prefer to collect the whole structure grouped by level just in one shot.

Also, i haven't any preference to use BDS or DFS at all, both are just fine. Here is my actual code:

function Node(code, parent) {
  this.code = code;
  this.children = [];
  this.parentNode = parent;
}
Node.prototype.addNode = function (code) {
  var l = this.children.push(new Node(code, this));
  return this.children[l-1];
};
Node.prototype.dfs = function (leafCallback) {
  var stack=[this], n, depth = 0;
  while(stack.length > 0) {
    n = stack.pop();
    if(n.children.length == 0) {
      if(leafCallback) leafCallback(n, this);
       continue;
    }
    for(var i=n.children.length-1; i>=0; i--) {
      stack.push(n.children[i]);
    }
    depth++; // ???
  }
};

var tree = new Node("ROOT");
tree.addNode("A1").addNode("A2").addNode("A3").addNode("A4");
tree.addNode("B1").addNode("B2").addNode("B3");
tree.addNode("C1").addNode("C2");

Answer 1

You can use recursion and passing node and depth as parameters

function Node(code, parent) {
  this.code = code;
  this.children = [];
  this.parentNode = parent;
}
Node.prototype.addNode = function (code) {
  var l = this.children.push(new Node(code, this));
  return this.children[l-1];
};

let result = [], depth = {};
function dfs(node){
    node.depth = 0;
    let stack = [node];
    while(stack.length > 0){
        let root = stack[stack.length - 1];
        let d = root.depth;
        result[d] = result[d] || [];
        result[d].push(root.code);
        stack.length--;
        for(let element of root.children){
            element.depth = root.depth + 1;
            stack.push(element);
        }
    }
}

var tree = new Node("ROOT");
tree.addNode("A1").addNode("A2").addNode("A3").addNode("A4");
tree.addNode("B1").addNode("B2").addNode("B3");
tree.addNode("C1").addNode("C2");

dfs(tree);

console.log(result.reverse());

Answer 2

It is possible to write this in a recursive way which would benefit from tail optimisation

function reduceTree(tree) {
    const getCode = n => n.code;
    const _reduce = (level = [tree], acc = [[getCode(tree)]], depth = 1) => {
        const children = level.reduce((a, e) => a.concat(e.children), []);
        if (!children.length) {
            return acc;
        }
        acc[depth] = children.map(getCode);
        return _reduce(children, acc, depth + 1);
    };
    return _reduce().reverse();
}

reduceTree(tree);
/*
[
    ["A4"],
    ["A3", "B3"],
    ["A2", "B2", "C2"],
    ["A1", "B1", "C1"],
    ["ROOT"]
]
*/

Answer 3

That's it - thanks to marvel308 for pointing out that there is required an additional helper node.depth

function Node(code, parent) {
  this.code = code;
  this.depth = -1;
  this.children = [];
  this.parentNode = parent;
}

Node.prototype.dfs= function() {
  var result = [], stack = [];
  this.depth = 0;
  stack.push(this);
  while(stack.length > 0) {
    var n = stack[stack.length - 1], i = n.depth;
    if(!result[i]) result.push([]);
    result[i].push(n); /* get node or node.code, doesn't matter */
    stack.length--;
    var children = n.children;
    /* keep the original node insertion order, by looping backward */
    for(var j = n.children.length - 1; j >= 0; j--) {
      var c = children[j];
      c.depth = n.depth + 1;
      stack.push(c);
    }
  }
  return result.reverse(); /* return an array */
};