Generating nested list from flat list with parent/child lists in JavaScript

Question

I'm building a web-app that needs to process nested geographical data to both display in a treeview, but also be searchable. The raw data looks something like this:

id:1, name:UK
id:2: name: South-East, parentId: 1
id:3: name: South-West, parentId:1
id:4: name: Berkshire, parentId: 2
id:5: name: Reading, parentId: 4

and I want it to look something like this:

id:1: name UK, children[ 
 {id: 2, name: South-East, children:[
    {id:4: name: Berkshire, children: [
       {id:5: name: Reading}
     ]
  }, 
   {id:3: name: South-West}
]

so that each geographical location has a "children" array property, which contains all the sub-areas, each of which has another "children" array property, and so on. It would probably make sense to have a "parent" property as well, so I could navigate from any child item up to its parent.

I also need to be able to search the list - searching each branch of the tree may take some time, so perhaps I need to also keep the list in flat format.

I know how I could do this in JavaScript (possibly using jLinq for filtering, grouping and sorting), but I don't know how fast it would be. Has anyone already had a go at this in JavaScript or know of any general algorithms/patterns that solve this?

Figured it out ... lazy loading. We don't need to display all the data at once, only on demand (it's a big ol' datastructure, and people are going to click through to their required bit). It'll be easier to lookup the related items and add them to the "children" property when needed, rather than do the whole lot in advance ... — TobyEvans
– TobyEvans, Commented Feb 16, 2011 at 13:33
Would you mind posting your solution as an answer below so we can get this off the Unanswered list? Thank you. — Bill the Lizard
– Bill the Lizard, Commented Jul 18, 2011 at 15:44

Mark Rhodes · Accepted Answer · 2013-01-09 12:30:27Z

1

It's actually not that difficult to make the flat array into a tree and do it pretty quickly, I think the slowest bit will be getting the definition of the data structure onto the page (hence why you're lazy loading was successful!). This can be helped though by making the data structure definition smaller.

In Javascript I did it like this:

    //Make the data definition as small as possible..
    //each entry is [ name, parent_pos_in_array]..
    //note: requires that a parent node appears before a child node..
    var data = [
        ["UK", -1], //root..
        ["South-East", 0],
        ["South-West", 0],
        ["Berkshire", 1],
        ["Reading", 3]
        //...etc...
    ];

    //Turns given flat arr into a tree and returns root..
    //(Assumes that no child is declared before parent)
    function makeTree(arr){
        //Array with all the children elements set correctly..
        var treeArr = new Array(arr.length);

        for(var i = 0, len = arr.length; i < len; i++){
            var arrI = arr[i];
            var newNode = treeArr[i] = {
                name: arrI[0],
                children: []
            };
            var parentI = arrI[1];
            if(parentI > -1){ //i.e. not the root..
                treeArr[parentI].children.push(newNode);
            }
        }
        return treeArr[0]; //return the root..
    }

    var root = makeTree(data);

To test the speed on a larger list you can run:

    var data = [['root', -1]];
    for(var i = 1; i < 100000; i++){
        var parentI = Math.floor(Math.random()*(i-1));
        data.push(['a_name', parentI]);   
    }
    var start = new Date().getTime();
    var tree = makeTree(data);
    var end = new Date().getTime();

    console.log('Took: ' + (end-start) + 'ms.');

With 100000 elements in the array it takes < 200ms on my old desktop. Not sure what kind of performance is acceptable though!

edited Jan 9, 2013 at 12:30

answered Jan 20, 2012 at 21:52

Mark Rhodes

10.2k4 gold badges52 silver badges51 bronze badges

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

2 Comments

Charles Over a year ago

This only work if data are sorted :( e.g. with such data: var data = [ ["South-East", 0], ["South-West", 0], ["Berkshire", 1], ["Reading", 3], ["UK", -1] ]; won't work...

Mark Rhodes Over a year ago

Well it requires that you don't define a child before a parent, which I think is reasonable. I've added a comment above to indicate that. It would be relatively easy to sort it first, but that would be extra processing.

Community · Accepted Answer · 2017-05-23 12:02:21Z

If you have a simple id & parent-id objects array with no other clue on the level, it's a tough task to generate the nested form. I would assume recursive approaches won't be practical in long lists. The best method that i could come up with so far is sorting that array in such a way that all children come after their parents. Parents and children and even the root objects can be mixed but a child must come after it's parent. Assuming that the object structure is like var data = [{id: KL442, pid: HN296}, {id: ST113, pid: HN296}, {id: HN296, pid: "root"},...] Yet sorting is the first phase of the job. While sorting we can generate a LUT (look up table) to access the parents almost at no cost. At the exit of the outer loop just one single instruction lut[a[i].id]=i; is sufficient for this. This makes the job enormously fast at the nesting stage. This is the sorting and LUT preparation phase.

function sort(a){
  var len = a.length,
      fix = -1;
  for (var i = 0; i < len; i++ ){
      while(!!~(fix = a.findIndex(e => a[i].pid == e.id)) && fix > i) [a[i],a[fix]] = [a[fix],a[i]];
      lut[a[i].id]=i;
  }
  return a;
}

Once you have it sorted than a reverse iteration is the only thing you have to do to get your nested structure. So that you now have your data array sorted and LUT prepared, then this is the code for nesting.

for (var i = sorted.length-1; i>=0; i--)
    sorted[i].pid != "root" && (!! sorted[lut[sorted[i].pid]].children
                                && sorted[lut[sorted[i].pid]].children.push(sorted.splice(i,1)[0])
                                || (sorted[lut[sorted[i].pid]].children = [sorted.splice(i,1)[0]]));

For a working sample you can check a previous answer of mine.

Yuri Gor · Accepted Answer · 2019-03-11 08:46:04Z

0

With Lodash:

var index = _.mapKeys(data,'id');
var obj = {};
_.each(index,function(v){
  if(!v.parentId){
    obj[v.id]=v;
  }else{
    if(!index[v.parentId].children){
      index[v.parentId].children=[];
    }
    index[v.parentId].children.push(v);
  }
});

Demo is here

answered Mar 11, 2019 at 8:46

Yuri Gor

1,4931 gold badge15 silver badges28 bronze badges

Collectives™ on Stack Overflow

Generating nested list from flat list with parent/child lists in JavaScript

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related