Javascript array sorting by level

Question

I have data with a one to many relationship in the same array. The organization is established by level. An element's parent is always one level higher than itself and is referenced by parentId.

How would you get a multi level array from this array? The elements with the highest level would be the main array, with their children as subarray in javascript?

[{
    _id: 100,
    level: 3,
    parentId: null,
},
{
    _id: 101,
    level: 2,
    parentId: 100,
},
{
    _id: 102,
    level: 2,
    parentId: 100,
},
{
    _id: 103,
    level: 2,
    parentId: 100,
},
{
    _id: 104,
    level: 1,
    parentId: 101,
},
{
    _id: 105,
    level: 1,
    parentId: 102,
},
{
    _id: 106,
    level: 1,
    parentId: 101,
},
{
    _id: 107,
    level: 1,
    parentId: 103,
},
{
    _id: 108,
    level: 1,
    parentId: 102,
},
{
    _id: 109,
    level: 1,
    parentId: 103,
}]

Expected output would be

                       100
                        |
       ------------------------------------
       |                |                 |
      101              102               103
    -------           ------            ------
    |     |           |    |            |    |
   104   106         105  108          107  109

Thanks

If I understand you ask for the preferred|suggested|best structure to contain such a data? If yes, first I would rather use low-to-high level from parent to children. — cFreed, Dec 01 '16 at 22:02
@MattBurland I dont really know where to start, tried getting the highest level then from there link the children but I think im missing the part where i need to create a new sub array. Dont if that makes sense to you — David Nathanael, Dec 01 '16 at 22:07
@cFreed Thats the output looking for, can't figure out the implementation. I should edit my question to make more clear. thanks — David Nathanael, Dec 01 '16 at 22:09

Ori Drori · Accepted Answer · 2016-12-01T22:09:49.950

Create a hash by id of the the nodes using Array#reduce, then iterate the array with Array.forEach(). If the parent id is null, it's the root, if not add it to the parent's children:

function createTree(data) {
  var tree = [];
  
  data.forEach(function(node) {
    var parentId = node.parentId;
    
    if(parentId === null) {
      tree.push(node);
    } else {
      (this[parentId].children || (this[parentId].children = [])).push(node);
    }
  }, data.reduce(function(hash, node) {
    hash[node._id] = node;
    
    return hash;
  }, Object.create(null)));
  
  return tree;
}

var data = [{
    _id: 100,
    level: 3,
    parentId: null,
},
{
    _id: 101,
    level: 2,
    parentId: 100,
},
{
    _id: 102,
    level: 2,
    parentId: 100,
},
{
    _id: 103,
    level: 2,
    parentId: 100,
},
{
    _id: 104,
    level: 1,
    parentId: 101,
},
{
    _id: 105,
    level: 1,
    parentId: 102,
},
{
    _id: 106,
    level: 1,
    parentId: 101,
},
{
    _id: 107,
    level: 1,
    parentId: 103,
},
{
    _id: 108,
    level: 1,
    parentId: 102,
},
{
    _id: 109,
    level: 1,
    parentId: 103,
}];

var result = createTree(data);

console.log(result);

is there any special reason to use `this[parentId].children || (this[parentId].children = []);` over `this[parentId].children = this[parentId].children || [];`? — Nina Scholz, Dec 01 '16 at 22:09
Thanks this does what i needed, going to learn those functions. — David Nathanael, Dec 01 '16 at 22:26

Nina Scholz · Answer 2 · 2016-12-01T22:12:18.970

You could make a tree out of the data, with a single loop. This proposal works for unsorted data as well.

var data = [{ _id: 100, level: 3, parentId: null }, { _id: 101, level: 2, parentId: 100 }, { _id: 102, level: 2, parentId: 100 }, { _id: 103, level: 2, parentId: 100 }, { _id: 104, level: 1, parentId: 101 }, { _id: 105, level: 1, parentId: 102 }, { _id: 106, level: 1, parentId: 101 }, { _id: 107, level: 1, parentId: 103 }, { _id: 108, level: 1, parentId: 102 }, { _id: 109, level: 1, parentId: 103 }],
    tree = function (data, root) {
        var r, o = Object.create(null);
        data.forEach(function (a) {
            a.children = o[a._id] && o[a._id].children;
            o[a._id] = a;
            if (a.parentId === root) {
                r = a;
            } else {
                o[a.parentId] = o[a.parentId] || {};
                o[a.parentId].children = o[a.parentId].children || [];
                o[a.parentId].children.push(a);
            }
        });
        return r;
    }(data, null);

console.log(tree);

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

Javascript array sorting by level

2 Answers2