JavaScript format array of objects into nested children

Question

I have an array of objects with parentId and sort values that I'd like to put into an array with nested 'children' and sorted appropriately.

For example, here's the data:

[{
    id: 1,
    sort: 2,
    parentId: null,
    name: 'A'
}, {
    id: 2,
    sort: 1,
    parentId: 1,
    name: 'A.1'
}, {
    id: 3
    sort: 2,
    parentId: 1,
    name: 'A.2'
}, {
    id: 4,
    sort: 1,
    parentId: null,
    name: 'B'
}]

The way I'd like to transform this would be such as:

[{
    id: 4,
    sort: 1,
    parentId: null,
    name: 'B',
    children: []
}, {
    id: 1,
    sort: 2,
    parentId: null,
    name: 'A',
    children: [{
        id: 2,
        sort: 1,
        parentId: 1,
        name: 'A.1'
    }, {
        id: 3
        sort: 2,
        parentId: 1,
        name: 'A.2'
    }]
}]

This is sorted (id 4 being at the top, since sort is 1) and the children are nested and also sorted accordingly.

Any suggestions on a good way to do this? I can recursively loop through to apply children, but not sure how I can maintain sorting on this.

Are the names one character long only? Is the first part of the name only alphabets as in A-Z or are there numbers and special characters? — stackErr
– stackErr, Commented Apr 13, 2016 at 17:05
@stackErr I think names do not matter at all here, you don't need them to answer the question. He added those for us to see more easily where everything should go. — blex
– blex, Commented Apr 13, 2016 at 17:09
@stackErr yeah the names are just for simplicity sake of the example. All logic would be based off id, parentId and sort. — dzm
– dzm, Commented Apr 13, 2016 at 17:15
There's only two, but probably it should support any level via recursion — dzm
– dzm, Commented Apr 13, 2016 at 17:20

Nina Scholz · Accepted Answer · 2016-04-15 09:56:07Z

3

This is a proposal which sorts first and filters after that.

The sorting takes the properties parentId and sort. This is necessary for the next step, because the "filtering" needs a sorted array.

Later the array is filterd with Array#filter(), Here is thisArgs used for referencing nodes for a possible insertation of children.

Edit: Update for unsorted (id/parentId) data.

var array = [{ id: 1, sort: 2, parentId: null, name: 'A' }, { id: 2, sort: 1, parentId: 1, name: 'A.1' }, { id: 3, sort: 2, parentId: 1, name: 'A.2' }, { id: 4, sort: 1, parentId: null, name: 'B' }],
    nested;

array.sort(function (a, b) {
    return (a.parentId || -1) - (b.parentId || -1) || a.sort - b.sort;
});

nested = array.filter(function (a) {
    a.children = this[a.id] && this[a.id].children;
    this[a.id] = a;
    if (a.parentId === null) {
        return true;
    }
    this[a.parentId] = this[a.parentId] || {};
    this[a.parentId].children = this[a.parentId].children || [];
    this[a.parentId].children.push(a);
}, Object.create(null));

document.write('<pre>' + JSON.stringify(nested, 0, 4) + '</pre>');

edited Apr 15, 2016 at 9:56

answered Apr 13, 2016 at 17:36

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

VonD Over a year ago

This doesn't always work, because it uses the parentId to sort the data, which is irrelevant. Try it with : [{id: 1, parentId: null, sort: 1}, {id: 2, parentId: 3, sort: 1}, {id: 3, parentId: 2, sort: 1}] and you'll find yourself with an exception. Other than that, the thisArg trick on filter is really nice.

Nina Scholz Over a year ago

your data is not valid. it has a circular reference. 2 -> 3, 3 -> 2

VonD Over a year ago

@NinaScholz Yes sorry, here's a better example:

[{id: 1, parentId: 4, sort: 1}, {id: 2, parentId: 3, sort: 1}, {id: 3, parentId: 1, sort: 1}, {id: 4, parentId: null, sort: 1}]

Nina Scholz Over a year ago

@VonD, please see edit, it should work now with (kind of) unsorted data.

blex · Accepted Answer · 2016-04-13 18:19:44Z

I gave it a try and came back, and there are already other answers, but I'm posting it anyway.

This method modifies the original Array:

var items = [{id: 1,sort: 2,parentId: null,name: 'A'}, {id: 2,sort: 1,parentId: 1,name: 'A.1'}, {id: 3,sort: 2,parentId: 1,name: 'A.2'}, {id: 4,sort: 1,parentId: null,name: 'B'}];


function generate_tree(arr){
  var references = {};
  arr.sort(function(a,b){
    // Save references to each item by id while sorting
    references[a.id] = a; references[b.id] = b;
    // Add a children property
    a.children = []; b.children = [];
    if(a.sort > b.sort) return 1;
    if(a.sort < b.sort) return -1;
    return 0;
  });

  for(var i=0; i<arr.length; i++){
    var item = arr[i];
    if(item.parentId !== null && references.hasOwnProperty(item.parentId)){
      references[item.parentId].children.push(arr.splice(i,1)[0]);
      i--; // Because the current index now contains the next item
    }
  }
  return arr;
}

document.body.innerHTML = "<pre>" + JSON.stringify(generate_tree(items), null, 4) + "</pre>";

Tudor Constantin · Accepted Answer · 2016-04-13 17:39:19Z

I'd create a new data structure, to look like:

{ 1: { id: 1, sort: 2, parentId: null, name: 'A' }, 2: { id: 4, sort: 1, parentId: null, name: 'B' } }

Things to notice: the new structure is an object, not an array, that contains only the topmost elements in it (the ones with parentId null)

Then, do a for over the original array, and assign new_obj[ orig_arr_curr_elem[parentId] ].children.push(orig_arr_curr_elem)
Then create a new array with the elems from new_obj sort() the (or the children property) however you want

Code that implements the steps 1 and 2 (run this using node):

var util = require('util');
var old_arr = [{
    id: 1,
    sort: 2,
    parentId: null,
    name: 'A'
}, {
    id: 2,
    sort: 1,
    parentId: 1,
    name: 'A.1'
}, {
    id: 3,
    sort: 2,
    parentId: 1,
    name: 'A.2'
}, {
    id: 4,
    sort: 1,
    parentId: null,
    name: 'B'
}];

var new_obj = {};
for (var i = 0; i < old_arr.length; i++){
    if ( old_arr[i].parentId == null )
        new_obj[ old_arr[i].id ] = old_arr[i];
}

for (var i = 0; i < old_arr.length; i++){
    if ( old_arr[i].parentId == null ) continue;
    new_obj[ old_arr[i].parentId ].children = new_obj[ old_arr[i].parentId ].children || [];
    new_obj[ old_arr[i].parentId ].children.push( old_arr[i] );
}

console.log(util.inspect(new_obj, {showHidden: false, depth: null}));

Collectives™ on Stack Overflow

JavaScript format array of objects into nested children

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related