I have an array of objects, Where each object has an id
and a ParentId
property (so they can be arranged in trees). They are in no particular order.
Please note that the id
's and parentId
's will not be integers, they will be strings (just wanted to have the sample code cleaner..)
There is only one root: lets say its id
:1
The data looks like so:
data = [
{
id:"id-2",
parentId:"id-3"
},
{
id:"id-4",
parentId:"2"
},
{
id:"id-3",
parentId:"id-4"
},
{
id:"id-5",
parentId:"id-4"
},
{
id:"id-6",
parentId:"id-1"
},
{
id:"id-7",
parentId:"id-1"
}
// and so on...
]
I am looking for a efficient way to give each object a level
property which should specify the nested level it is...
They should then look like this:
data = [
{
id:"id-2",
parentId:"id-1",
level:2
},
{
id:"id-3",
parentId:"id-4",
level:5
},
{
id:"id-4",
parentId:"id-2",
level:3
},
{
id:"id-5",
parentId:"id-4",
level:5
},
{
id:"id-6",
parentId:"id-1",
level:2
},
{
id:"id-7",
parentId:"id-3",
level:4
}
// and so on...
]
In short:
I want that level
to be added dynamically via looping thru the array and figuring out the hierarchy..
Additionally, (if posible) they should then be sorted according to there order, like for instance all objects level:3
's from the same parent should be next to each other, not that there should be siblings of the same parent next to each other rather then two cousins of level 3 next to each other.
One way to address this without the need for recursion is to create a DOM hierarchy. For each item in the array, create a div and attach it to its parent. then walk the DOM and assign the levels (top is level 1, then add 1 for each child).
I have set up a rough demo here: http://jsfiddle.net/4AqgM/
An excerpt from the code:
Here is your working code. Level starts at 2.
ALERT: If a level cannot be calculated, the application may go into an infinite loop. So, make sure the
parentId
is valid for all objects and at least one of them haveparentId="id-1"
.I'm not sure where you get the value for
level
so I'll assume that its just an integer. BTW, you can add the level property to each of your array's item by looping through it.which will give
A working example of the below code is on jsFiddle.
Index the tree by id and traverse it upwards, from each node, and count until you hit the root. By indexing first, we approach O(n) time complexity (depending on tree density). ****Updated to satisfy the sorting requirement, and allow exclusion of root node***:
Example:
Output:
Note
If you change the input order, the sort comes out a little different, but it's still correct (i.e., in level-order, grouped by sibling).