Get the level of a hierarchy

Question

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.

There is one root, lets say its `parentId`:1 (will be a string) — adardesign, Jan 03 '13 at 04:22
What will be thed id and parentId of the root element? What should be the level for that element? — ATOzTOA, Jan 03 '13 at 04:27
I Updated the description to be clearer.. thanks for your input — adardesign, Jan 03 '13 at 04:31

Joe Coder · Accepted Answer · 2013-01-04T20:22:04.663

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***:

function levelAndSort(data, startingLevel) {
    // indexes
    var indexed = {};        // the original values
    var nodeIndex = {};      // tree nodes
    var i;
    for (i = 0; i < data.length; i++) {
        var id = data[i].id;
        var node = {
            id: id,
            level: startingLevel,
            children: [],
            sorted: false
        };
        indexed[id] = data[i];
        nodeIndex[id] = node;
    }

    // populate tree
    for (i = 0; i < data.length; i++) {
        var node = nodeIndex[data[i].id];
        var pNode = node;
        var j;
        var nextId = indexed[pNode.id].parentId;
        for (j = 0; nextId in nodeIndex; j++) {
            pNode = nodeIndex[nextId];
            if (j == 0) {
                pNode.children.push(node.id);
            }
            node.level++;
            nextId = indexed[pNode.id].parentId;
        }
    }

    // extract nodes and sort-by-level
    var nodes = [];
    for (var key in nodeIndex) {
        nodes.push(nodeIndex[key]);
    }
    nodes.sort(function(a, b) {
        return a.level - b.level;
    });

    // refine the sort: group-by-siblings
    var retval = [];
    for (i = 0; i < nodes.length; i++) {
        var node = nodes[i];
        var parentId = indexed[node.id].parentId;
        if (parentId in indexed) {
            var pNode = nodeIndex[parentId];
            var j;
            for (j = 0; j < pNode.children.length; j++) {
                var child = nodeIndex[pNode.children[j]];
                if (!child.sorted) {
                    indexed[child.id].level = child.level;
                    retval.push(indexed[child.id]);
                    child.sorted = true;
                }
            }
        }
        else if (!node.sorted) {
            indexed[node.id].level = node.level;
            retval.push(indexed[node.id]);
            node.sorted = true;
        }
    }
    return retval;
}

Example:

// level 0 (root) excluded
var startingLevel = 1;
var someData = [
    {id : "id-1", parentId : "id-0"},
    {id : "id-2", parentId : "id-0"},
    {id : "id-3", parentId : "id-2"},
    {id : "id-4", parentId : "id-3"},
    {id : "id-5", parentId : "id-4"},
    {id : "id-6", parentId : "id-4"},
    {id : "id-7", parentId : "id-0"},
    {id : "id-8", parentId : "id-1"},
    {id : "id-9", parentId : "id-7"},
    {id : "id-10", parentId : "id-1"},
    {id : "id-11", parentId : "id-1"},
    {id : "id-12", parentId : "id-1"}
];
var outputArray = levelAndSort(someData, startingLevel);

Output:

enter image description here

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).

Looks great! is there a option to omit the actual root? (in your data its the first one..) — adardesign, Jan 04 '13 at 17:41

score 2 · Answer 2 · answered Jan 03 '13 at 04:14

2

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.

for (var i = 0, l = data.length; i < l; i++) { 
    data[i].level = i
}

which will give

data = [{id:"1", parentId:"3", level:0 }, {id:"2", parentId:"1", level:1 } ...]

answered Jan 03 '13 at 04:14

Anthony

589
3
15

I want the `level` to be added dynamically via looping thru the array and figuring out the hierarchy, also as i specified that the `id`'s wont be a integer, they will be a string – adardesign Jan 03 '13 at 04:16
so what you mean is figure out how deep the element with this id inside this parent? and assign it to the level property? – Anthony Jan 03 '13 at 04:23
using jQuery on the same for loop above `data[i].level = $(data[i].id).parentsUntil($(data[i].parentId)).length + 1;` – Anthony Jan 03 '13 at 04:29
@Mark Dee Thanks, But the `id`'s and `parentId`'s are not integers, they will be strings.. – adardesign Jan 03 '13 at 04:35

score 1 · Answer 3 · answered Jan 03 '13 at 06:18

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 have parentId="id-1".

<script type="text/javascript">
    data = [
        {
            id:"id-2",
            parentId:"id-3"
        },
        {
            id:"id-4",
            parentId:"id-2"
        },
        {
            id:"id-3",
            parentId:"id-5"
        },
        {
            id:"id-5",
            parentId:"id-1"
        }
    ];

    function processData() {
        flag = true;

        while(flag) {
            flag = false;

            for(var i = 0; i < data.length; i++) {
                if(data[i].parentId == "id-1") {
                    data[i].level = 2;
                } else {
                    l = getLevel(data[i].parentId);
                    if(l > 0) {
                        data[i].level = l + 1;
                    } else {
                        flag = true;
                    }
                }
            }
        }
    }

    function getLevel(id) {
        for(var i = 0; i < data.length; i++) {
            if(data[i].id == id) {
                if(data[i].level) {
                    return data[i].level;
                } else {
                    return 0;
                }
            }
        }

        return 0;
    }

    processData();

    console.log(data);

</script>

score 1 · Answer 4 · answered Jan 03 '13 at 18:30

1

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:

top.dataset.level="1";
var topChildren=top.getElementsByTagName("div");
for (var i=0;i<topChildren.length;i++) {
topChildren[i].dataset.level=parseInt(topChildren[i].parentNode.dataset.level)+1;
}

answered Jan 03 '13 at 18:30

Christophe

27,383
28
97
140

@adardesign sorry, I am not sure to understand. The divs are just an intermediary step and not meant to stay. Your question doesn't say that you want any (nested or not). – Christophe Jan 03 '13 at 18:58
1

Clever way to use the DOM as a data structure, but redundant because the tree already exists as a series of `parentId` references. – Joe Coder Jan 03 '13 at 19:38
1

@JoeCoder agree about the redundancy. My approach would be interesting if the purpose of the levels (not explained in the question) was to build a DOM tree. – Christophe Jan 03 '13 at 19:51
@Christophe, Correct, the purpose is to eventually build a DOM, but not a nested one, I will be generating a flat DOM parents next to children... – adardesign Jan 04 '13 at 00:33
@adardesign I see. I have slightly modified my demo to un-nest the divs at the end, hope this helps: http://jsfiddle.net/4AqgM/3/ . Again, this is rough code with room for optimization... – Christophe Jan 04 '13 at 02:20

Get the level of a hierarchy

In short:

4 Answers4

Example:

Output:

Note

Linked