create javascript tree out of list of objects

Question

I would like to 'translate' a list of objects into a json format edible by jstree:

data = [
 { 
 "data" : { 
 "title" : "father",
 "attr" : { "href" : "#" }
 },
 "children" : [
 { 
 "data" : { 
 "title" : "Older Son",
 "attr" : { "href" : "#" }
 },
 "children" : []
 },
 { 
 "data" : { 
 "title" : "Younger Son",
 "attr" : { "href" : "#" }
 },
 "children" : []
 }
 ]
 },
]

My input looks like this:

[
Object
id: 35
name: "bnm,bnm"
parent_id: null
, 
Object
id: 36
name: "ghk"
parent_id: 35
, 
Object
id: 37
name: "hgkgh"
parent_id: null
, 
Object
id: 38
name: "jklhjk"
parent_id: null
, 
Object
id: 39
name: "fghdfgh"
parent_id: 38
, 
Object
id: 40
name: "bsdbd"
parent_id: 38
,
...]

Well, to be honest, this would not be a tree, rather a forest. But it doesn't matter.

I've spent quite a lot of time on it, but failed to get it working. Operating on arrays seems to be nasty in javascript (in comparison to Java,C++ or PHP)...

What I've tried so far is:

1. (pre) the source data (list of objects) meet one condition: a son can't be present before it's parent
2. make it associative array (key=id, value=object), so it had to be string-keyed.
3. pop last array element and push it inside its parent element's children array. Repeat this for all non-null-parent elements.
4. hoped this should work.

• Felix Kling: Please post what you have tried so far. It might make it easier for us to help you.
• elclanrs: I find PHP arrays nastier than JavaScript arrays. JS is very lean. What are you trying to do and what didn't work, I don't quite get it...
• ducin: I've edited my post and described the algorithm idea. I know I should write on stacoverflow what I've tried so far -but I'm not experienced in JS and my code looked so ugly that it could make no sense to paste it here :/...

Answer 1

You'll want to first put all of your items into a sparse array indexed by their ID and translate everything except the children (which should be present but empty) and including the parent ID:

var itemsByID = [];
items.forEach(function(item) {
 itemsByID[item.id] = {
 data: {title: item.name},
 children: [],
 parentID: item.parent_id
 };
});

Then you'll want to go through all of the items, adding children to their parents:

itemsByID.forEach(function(item) {
 if(item.parentID !== null) {
 itemsByID[item.parentID].children.push(item);
 }
});

Then find the roots:

var roots = itemsByID.filter(function(item) { return item.parentID === null; });

Then clean the items up by removing the parent ID:

itemsByID.forEach(function(item) { delete item.parentID; });

The roots of the tree will be in roots.

---

The reason your method didn't work is that if any children have a parent with a greater ID number, the parent element will not exist; you have already processed and popped it. You must leave all items in the array until you're done.

• icktoofay: For simplicity, I am using a number of methods of arrays that may not be available in older browsers. These methods can be safely shimmed or the code modified to not use these methods.
• ducin: well, I've tried your algorithm, but I don't like that JS inserts undefined into "holes" in the array (in fact, I wanted a typical map structure in the intermediate phase). So I decided to create a string-keyed array.
• icktoofay: @tkoomzaaskz: It's not array-specific. Accessing a nonexistent property on an object yields undefined. Furthermore, properties on all objects (including arrays) are string-keyed; it's just that the array's properties are string representations of the numbers. (When you do a[b] with an integer b, it is coerced into a string.)
• ducin: maybe my chrome javascript console made me think the array is different than it really is (and this led me to think that it fills holes with undefined). Anyway, thanks a lot!
• icktoofay: @tkoomzaaskz: Well, it kind of does; the holes aren't necessarily represented in memory, but they could be. It doesn't matter, since it'll be undefined if it's explicitly set to undefined or it'll be set to undefined if it's not explicitly defined.

Answer 2

Maybe unsplay does the trick?

>> var unsplay = require('unsplay');
>> unsplay([{id: 0}, {id: 1, pid: 0}], 'id', 'pid');
[{
 item: {id: 0},
 children: [{
 item: {id: 1, pid: 0},
 children: []
 }]
}]

(DISCLAIMER: I am the author)