Tree Structure from Adjacency List

Question

I am trying to generate a hierarchical tree object from a flat array with parent IDs.

// `parent` represents an ID and not the nesting level.
var flat = [
    { id: 1, name: "Business", parent: 0 },
    { id: 2, name: "Management", parent: 1 },
    { id: 3, name: "Leadership", parent: 2 },
    { id: 4, name: "Finance", parent: 1 },
    { id: 5, name: "Fiction", parent: 0 },
    { id: 6, name: "Accounting", parent: 1 },
    { id: 7, name: "Project Management", parent: 2  }
];

The final tree object should look as follows:

{ 
    id: 1, 
    name: "Business", 
    children: [
        { 
            id: 2, 
            name: "Management", 
            children: [
                { id: 3, name: "Leadership" },
                { id: 7, name: "Project Management" }
            ]
        }
        // [...]
    ]
}
// [...]

You can see my current work on this fiddle, but it only works on the first two levels.

I thought about collecting the orphans (objects from flat without a parent in tree yet) and then looping over them again to see if they now have a parent. But that could mean many loops over the tree object, especially with many categories over multiple levels.

I'm sure there is a more elegant solution.

Answer 1

Looks like you can do this in 2 passes no matter the tree depth:

var flat = [
    { id: 1, name: "Business", parent: 0 },
    { id: 2, name: "Management", parent: 1 },
    { id: 3, name: "Leadership", parent: 2 },
    { id: 4, name: "Finance", parent: 1 },
    { id: 5, name: "Fiction", parent: 0 },
    { id: 6, name: "Accounting", parent: 1 },
    { id: 7, name: "Project Management", parent: 2  }
];

var nodes = [];
var toplevelNodes = [];
var lookupList = {};

for (var i = 0; i < flat.length; i++) {
    var n = {
        id: flat[i].id,
        name: flat[i].name,
        parent_id: ((flat[i].parent == 0) ? null : flat[i].parent),
        children: []
        };
    lookupList[n.id] = n;
    nodes.push(n);
    if (n.parent_id == null) {
        toplevelNodes.push(n);
    }
}

for (var i = 0; i < nodes.length; i++) {
  var n = nodes[i];
  if (!(n.parent_id == null)) {
      lookupList[n.parent_id].children = lookupList[n.parent_id].children.concat([n]);
  }
}

console.log(toplevelNodes);

Answer 2

Update 2, (six years later)

I happened to stumble across this again and realized how much simpler this can be with a little ES6 destructuring and a straightforward recursion:

const makeForest = (id, xs) => 
  xs .filter (({parent}) => parent == id)
     .map (({id, parent, ...rest}) => ({id, ...rest, children: makeForest (id, xs)}))

var flat = [{id: 1, name: "Business", parent: 0}, {id: 2, name: "Management", parent: 1}, {id: 3, name: "Leadership", parent: 2}, {id: 4, name: "Finance", parent: 1}, {id: 5, name: "Fiction", parent: 0}, {id: 6, name: "Accounting", parent: 1}, {id: 7, name: "Project Management", parent: 2}];

console .log (
  makeForest (0, flat)
)

.as-console-wrapper {min-height: 100% !important; top: 0}

Note the name change. We're not making a tree, but an entire forest of trees, with each direct child of the root its own node. It would be relatively trivial to change this to generate a tree, if you had a structure to use for the root. Also note that this will let us find the tree rooted at any id. It doesn't have to be the overall root.

Performance

This does, as you worried about, have a worst-case performance of O(n^2). The actual run time is something like O(n * p) where p is the number of distinct parent nodes in the list. So we only approach the worst case when we have a tree nearly as deep as the length of the list. I would use something like this unless and until I could show that it was a hot spot in my code. My guess is that I would never find a need to replace it.

Lesson

Never count out recursion. This is significantly simpler than any of the other answers here, including my two versions below.

---

Update 1

I was not happy with extra complexity in my original solution. I'm adding another version that reduces that complexity. It manages to build the data in a single pass. It also gives one the chance to restructure the records in the trees differently from their original format if necessary. (By default, it only removes the parent node.)

Updated Version

Available on JSFiddle.

var makeTree = (function() {
    var defaultClone = function(record) {
        var newRecord = JSON.parse(JSON.stringify(record));
        delete newRecord.parent;
        return newRecord;
    };
    return function(flat, clone) {
        return flat.reduce(function(data, record) {
            var oldRecord = data.catalog[record.id];
            var newRecord = (clone || defaultClone)(record);
            if (oldRecord && oldRecord.children) {
                newRecord.children = oldRecord.children;
            }
            data.catalog[record.id] = newRecord;
            if (record.parent) {
                var parent = data.catalog[record.parent] = 
                        (data.catalog[record.parent] || {id: record.parent});
                (parent.children = parent.children || []).push(newRecord);
            } else {
                data.tree.push(newRecord);
            }
            return data;
        }, {catalog: {}, tree: []}).tree;
    }
}());

Note that this will work regardless of the order of the flat list -- the parent nodes do not have to precede their children -- although there is nothing in here to sort the nodes.

---

Original Version

My solution (also on JSFiddle):

var makeTree = (function() {
    var isArray = function(obj) {return Object.prototype.toString.call(obj) == "[object Array]"; };
    var clone = function(obj) {return JSON.parse(JSON.stringify(obj));};
    var buildTree = function(catalog, structure, start) {
        return (structure[start] || []).map(function(id, index) {
            var record = catalog[id];
            var keys = structure[start][index];
            var children = isArray(keys) ? keys.map(function(key) {
                return buildTree(catalog, structure, key);
            }) : buildTree(catalog, structure, keys);
            if (children.length) {
                record.children = children;
            }
            return record;
        })
    };
    return function(flat) {
        var catalog = flat.reduce(function(catalog, record) {
            catalog[record.id] = clone(record);
            delete(catalog[record.id].parent);
            return catalog;
        }, {});
        var structure = flat.reduce(function(tree, record) {
            (tree[record.parent] = tree[record.parent] || []).push(record.id);
            return tree;
        }, {});
        return buildTree(catalog, structure, 0); // this might be oversimplified.
    }
}());