I have a complex json file that I have to handle with javascript to make it hierarchical, in order to later build a tree. Every entry of the json has : id : a unique id, parentId : the id of the parent node (which is 0 if the node is a root of the tree) level : the level of depth in the tree
The json data is already "ordered". I mean that an entry will have above itself a parent node or brother node, and under itself a child node or a brother node.
Input :
{
"People": [
{
"id": "12",
"parentId": "0",
"text": "Man",
"level": "1",
"children": null
},
{
"id": "6",
"parentId": "12",
"text": "Boy",
"level": "2",
"children": null
},
{
"id": "7",
"parentId": "12",
"text": "Other",
"level": "2",
"children": null
},
{
"id": "9",
"parentId": "0",
"text": "Woman",
"level": "1",
"children": null
},
{
"id": "11",
"parentId": "9",
"text": "Girl",
"level": "2",
"children": null
}
],
"Animals": [
{
"id": "5",
"parentId": "0",
"text": "Dog",
"level": "1",
"children": null
},
{
"id": "8",
"parentId": "5",
"text": "Puppy",
"level": "2",
"children": null
},
{
"id": "10",
"parentId": "13",
"text": "Cat",
"level": "1",
"children": null
},
{
"id": "14",
"parentId": "13",
"text": "Kitten",
"level": "2",
"children": null
},
]
}
Expected output :
{
"People": [
{
"id": "12",
"parentId": "0",
"text": "Man",
"level": "1",
"children": [
{
"id": "6",
"parentId": "12",
"text": "Boy",
"level": "2",
"children": null
},
{
"id": "7",
"parentId": "12",
"text": "Other",
"level": "2",
"children": null
}
]
},
{
"id": "9",
"parentId": "0",
"text": "Woman",
"level": "1",
"children":
{
"id": "11",
"parentId": "9",
"text": "Girl",
"level": "2",
"children": null
}
}
],
"Animals": [
{
"id": "5",
"parentId": "0",
"text": "Dog",
"level": "1",
"children":
{
"id": "8",
"parentId": "5",
"text": "Puppy",
"level": "2",
"children": null
}
},
{
"id": "10",
"parentId": "13",
"text": "Cat",
"level": "1",
"children":
{
"id": "14",
"parentId": "13",
"text": "Kitten",
"level": "2",
"children": null
}
}
]
}
There is an efficient solution if you use a map-lookup. If the parents always come before their children you can merge the two for-loops. It supports multiple roots. It gives an error on dangling branches, but can be modified to ignore them. It doesn't require a 3rd-party library. It's, as far as I can tell, the fastest solution.
function list_to_tree(list) {
var map = {}, node, roots = [], i;
for (i = 0; i < list.length; i += 1) {
map[list[i].id] = i; // initialize the map
list[i].children = []; // initialize the children
}
for (i = 0; i < list.length; i += 1) {
node = list[i];
if (node.parentId !== "0") {
// if you have dangling branches check that map[node.parentId] exists
list[map[node.parentId]].children.push(node);
} else {
roots.push(node);
}
}
return roots;
}
var entries = [{
"id": "12",
"parentId": "0",
"text": "Man",
"level": "1",
"children": null
},
{
"id": "6",
"parentId": "12",
"text": "Boy",
"level": "2",
"children": null
},
{
"id": "7",
"parentId": "12",
"text": "Other",
"level": "2",
"children": null
},
{
"id": "9",
"parentId": "0",
"text": "Woman",
"level": "1",
"children": null
},
{
"id": "11",
"parentId": "9",
"text": "Girl",
"level": "2",
"children": null
}
];
console.log(list_to_tree(entries));
If you're into complexity theory this solution is Θ(n log(n)). The recursive-filter solution is Θ(n^2) which can be a problem for large data sets.