Can anyone help converting the following list of parent-child objects:
[ { "name":"root", "_id":"root_id", }, { "name":"a1", "parentAreaRef":{ "id":"root_id", }, "_id":"a1_id", }, { "name":"a2", "parentAreaRef":{ "id":"a1_id", }, "_id":"a2_id", }, { "name":"a3", "parentAreaRef":{ "id":"a2_id", }, "_id":"a3_id", }, { "name":"b1", "parentAreaRef":{ "id":"root_id", }, "_id":"b1_id", }, { "name":"b2", "parentAreaRef":{ "id":"b1_id", }, "_id":"b2_id", }, { "name":"b3", "parentAreaRef":{ "id":"b1_id", }, "_id":"b3_id", } ]
into a tree structure showing the parent-child relationship:
[ { "name": "root", "_id":"root_id", "children": [ { "name": "a1", "_id":"a1_id", "children" : [ { "name" : "a2", "_id":"a2_id", "children" : [ { "name" : "a3" "_id":"a3_id" } ] } ] }, { "name": "b1", "_id":"b1_id", "children" : [ { "name" : "b2" "_id":"b2_id" }, { "name" : "b3" "_id":"b3_id" } ] } ] } ]
(The output structure is an array to allow for multiple roots but if we can get a solution that handles a single root that's great too.)
The output tree looks like this:
root | -- a1 | | | -- a2 | | | -- a3 | -- b1 | -- b2 -- b3
Thanks!
I have a solution that works. I can give you hints as far as solving it. The good thing is that your data doesn't contain any forward references to nodes. So you can create your tree with just one pass through the array. If note, you will need to make a pass through the entire array first to build up a map of ids to nodes.
Your algorithm will look like this.
children
property (an array) to this node.children
array).This should help you solve the problem. If you're having specific issues with this algorithm I can point out where the problems are and how to solve it or post the solution and explain how I solved it.
UPDATE
I looked at the solution that you have. You actually don't need recursion for this and you can do this iteratively using the algorithm I described above. You are also modifying the structure in-place, which makes the algorithm more complicated. But you're somewhat on the right track. Here is how I solved it:
var idToNodeMap = {}; //Keeps track of nodes using id as key, for fast lookup
var root = null; //Initially set our loop to null
//loop over data
data.forEach(function(datum) {
//each node will have children, so let's give it a "children" poperty
datum.children = [];
//add an entry for this node to the map so that any future children can
//lookup the parent
idToNodeMap[datum._id] = datum;
//Does this node have a parent?
if(typeof datum.parentAreaRef === "undefined") {
//Doesn't look like it, so this node is the root of the tree
root = datum;
} else {
//This node has a parent, so let's look it up using the id
parentNode = idToNodeMap[datum.parentAreaRef.id];
//We don't need this property, so let's delete it.
delete datum.parentAreaRef;
//Let's add the current node as a child of the parent node.
parentNode.children.push(datum);
}
});
Now root
points to the entire tree.
Fiddle.
For the case where the array of elements is in arbitrary order, you will have to initialize idToNodeMap
first. The rest of the algorithm remains more-or-less the same (except for the line where you store the node in the map; that's not needed because you did it already in the first pass):
var idToNodeMap = data.reduce(function(map, node) {
map[node._id] = node;
return map;
}, {});
I know it's late, but I just finished this algorithm and maybe it can help some other people looking to solve the same problem: http://jsfiddle.net/akerbeltz/9dQcn/
A good thing about it is that it doesn't requires any special sort on the original object.
If you need to adapt it to your needs change the following lines:
Change the _id and the parentAreaRef.id depending on your structure.
if (String(tree[i]._id) === String(item.parentAreaRef.id)) {
Change the parentAreaRef depending on your structure.
if (tree[idx].parentAreaRef) buildTree(tree, tree.splice(idx, 1)[0])
Hope it helps!
UPDATE
Adding code here based on @Gerfried comment:
var buildTree = function(tree, item) {
if (item) { // if item then have parent
for (var i=0; i<tree.length; i++) { // parses the entire tree in order to find the parent
if (String(tree[i]._id) === String(item.parentAreaRef.id)) { // bingo!
tree[i].childs.push(item); // add the child to his parent
break;
}
else buildTree(tree[i].childs, item); // if item doesn't match but tree have childs then parses childs again to find item parent
}
}
else { // if no item then is a root item, multiple root items are supported
var idx = 0;
while (idx < tree.length)
if (tree[idx].parentAreaRef) buildTree(tree, tree.splice(idx, 1)[0]) // if have parent then remove it from the array to relocate it to the right place
else idx++; // if doesn't have parent then is root and move it to the next object
}
}
for (var i=0; i<data.length; i++) { // add childs to every item
data[i].childs = [];
}
buildTree(data);
console.log(data);
Thanks!
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With