score:45

Accepted answer

Here's one implementation, in Javascript: http://jsfiddle.net/9FqKS/

You start by creating a name-based map for easy lookup. There are a few different ways to do this - in this case, I use a .reduce method, which starts with an empty object and iterates over the data array, adding an entry for each node:

// create a {name: node} map
var dataMap = data.reduce(function(map, node) {
    map[node.name] = node;
    return map;
}, {});

This is equivalent to:

var dataMap = {};
data.forEach(function(node) {
    dataMap[node.name] = node;
});

(I sometimes think the reduce is more elegant.) Then iteratively add each child to its parents, or to the root array if no parent is found:

// create the tree array
var tree = [];
data.forEach(function(node) {
    // find parent
    var parent = dataMap[node.parent];
    if (parent) {
        // create child array if it doesn't exist
        (parent.children || (parent.children = []))
            // add node to parent's child array
            .push(node);
    } else {
        // parent is null or missing
        tree.push(node);
    }
});

Unless your tree is enormous, I don't think this should be too expensive, so you ought to be able to do it on the client side (if you can't, you might have too much data to easily display in any case).


Related Query

More Query from same tag