Generate Tree From Flat Array Javascript

I have an array as follow arr = [ { id: 1, name: 'Node1', level: 1 }, { id: 2, name: 'Node2', level: 2 }, {

Solution 1:

You could use the level property for indicating the nested position in a helper array. Then iterate the data and build children nodes if necessary.

functiongetTree(array) {
    var levels = [{}];
    array.forEach(function (a) {
        levels.length = a.level;
        levels[a.level - 1].nodes = levels[a.level - 1].nodes || [];
        levels[a.level - 1].nodes.push(a);
        levels[a.level] = a;
    });
    return levels[0].nodes;
}

console.log(getTree([{ id: 1, name: 'Node1', level: 1 }, { id: 2, name: 'Node2', level: 2 }, { id: 3, name: 'Node3', level: 3 }, { id: 4, name: 'Node4', level: 4 }, { id: 5, name: 'Node5', level: 5 }]));
console.log(getTree([{ id: 1, name: 'Node 1', level: 1 }, { id: 2, name: 'Node 1.1', level: 2 }, { id: 3, name: 'Node 1.1.1', level: 3 }, { id: 4, name: 'Node 1.1.1.1', level: 4 }, { id: 5, name: 'Node 1.2', level: 2 }, { id: 6, name: 'Node 1.2.1', level: 3 }, ]));

.as-console-wrapper { max-height: 100%!important; top: 0; }

Solution 2:

Well, as per our mutual commenting under @Nina Scholz's answer I believe this is an interesting question. We will have to create a nested structure not depending on the parental relationship among the objects but the level relationship among each object and the tree structure. Which means an object with level property as n should be present under all branches with at least n-1 levels.

So thanks to objects being reference types, as in parental relationship, we can still do this job with O(n) time complexity by using a single .reduce().

Here is my approach;

var data = [{ id: 1, name: 'Node1', level: 1 }, { id: 2.1, name: 'Node2.1', level: 2 }, { id: 2.2, name: 'Node2.2', level: 2 }, { id: 3.1, name: 'Node3.1', level: 3 }, { id: 3.2, name: 'Node3.2', level: 3 }, { id: 4, name: 'Node4', level: 4 }],
    tree = data.reduce(function(r,o,i){
                         r.prt = o.level-1;
                         r[r.prt] ? r[r.prt][0].children.push(o)
                                  : r[r.prt] = [{id: 0, name: "Root", level: r.prt, children: [o]}];
                         r[o.level] = r[o.level] ? (o.children = r[o.level][0].children,
                                                    r[o.level][0].id === 0 ? r[o.level][0] = o
                                                                           : r[o.level].push(o),
                                                    r[o.level])
                                                 : [Object.assign(o, {children: []})];
                         return r;
                       }, {prt: void0});
console.log(JSON.stringify(tree[0],null,4));

.as-console-wrapper { max-height: 100%!important; top: 0; }