Convert parent-child array to tree

Question

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!

Answer 1

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.

1. Create a map that maps id's to nodes. This will make it easy to look up nodes.
2. Loop through the array of nodes.
3. For each element.
   1. Add an entry into the map.
   2. Add a children property (an array) to this node.
   3. Does the element have a parent? If not it must be the root, so assign the this element to the root of the tree.
   4. This element has a parent, so look up the parent node, and then add this current node as a child of the parent node (add it to the 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;
}, {});

Answer 2

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:

1. Change the _id and the parentAreaRef.id depending on your structure.

   if (String(tree[i]._id) === String(item.parentAreaRef.id)) {

2. 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!

Answer 3

I know I'm too late, but since I just finished my contribution to a sample implementation of how this can be done I thought I would share it, since it might be found useful / or give inspiration to an alternative solution.

The implementation can be found here: http://jsfiddle.net/sw_lasse/9wpHa/

The main idea of the implementation centers around the following recursive function:

// Get parent of node (recursive)
var getParent = function (rootNode, rootId) {

    if (rootNode._id === rootId)
        return rootNode;

    for (var i = 0; i < rootNode.children.length; i++) {
        var child = rootNode.children[i];
        if (child._id === rootId)
            return child;

        if (child.children.length > 0)
            var childResult = getParent(child, rootId);

        if (childResult != null) return childResult;
    }
    return null;
};

... that is used to build the tree.

Answer 4

You can use array-to-tree module from npm.

Answer 5

Borrowing the caching logic from Vivin Paliath's answer, I have created a reusable function to convert a list of data with child-parent relationships into a tree.

var data = [
  { "id" : "root"                     },
  { "id" : "a1",   "parentId" : "root", },
  { "id" : "a2",   "parentId" : "a1",   },
  { "id" : "a3",   "parentId" : "a2",   },
  { "id" : "b1",   "parentId" : "root", },
  { "id" : "b2",   "parentId" : "b1",   },
  { "id" : "b3",   "parentId" : "b1",   }
];
var options = {
  childKey  : 'id',
  parentKey : 'parentId'
};
var tree = walkTree(listToTree(data, options), pruneChildren);

document.body.innerHTML = '<pre>' + JSON.stringify(tree, null, 4) + '</pre>';

function listToTree(list, options) {
  options = options || {};
  var childKey    = options.childKey    || 'child';
  var parentKey   = options.parentKey   || 'parent';
  var childrenKey = options.childrenKey || 'children';
  var nodeFn      = options.nodeFn      || function(node, name, children) {
    return { name : name, children : children };
  };
  var nodeCache = {};
  return list.reduce(function(tree, node) {
    node[childrenKey] = [];
    nodeCache[node[childKey]] = node;
    if (typeof node[parentKey] === 'undefined' || node[parentKey] === '') {
      tree = nodeFn(node, node[childKey], node[childrenKey]);
    } else {
      parentNode = nodeCache[node[parentKey]];
      parentNode[childrenKey].push(nodeFn(node, node[childKey], node[childrenKey]));
    }
    return tree;
  }, {});
}

function walkTree(tree, visitorFn, parent) {
  if (visitorFn == null || typeof visitorFn !== 'function') {
    return tree;
  }
  visitorFn.call(tree, tree, parent);
  if (tree.children && tree.children.length > 0) {
    tree.children.forEach(function(child) {
      walkTree(child, visitorFn, tree);
    });
  }
  return tree;
}

function pruneChildren(node, parent) {
  if (node.children.length < 1) {
    delete node.children;
  }
}

Answer 6

Give it a try:

   var obj = {};
   obj.rootElements = [];
   var currentRoot;
   var currentParent;
   for (s in a) {
       var t = a[s];
       var id = t._id;
       if (t.parentAreaRef) {
           var parentId = t.parentAreaRef.id;
           if (parentId == currentParent._id) {
               //add children
               if (!currentParent.children) {
                   currentParent.children = [];
               }
               currentParent.children.push(t);
           }
           else {
               addChildToParent(t, parentId);
           }

       }
       else // is root
       {
           currentRoot = t;
           currentParent = t;
           obj.rootElements.push(currentRoot);
       }
   }

   var t = currentRoot

   function addChildToParent(child, parentId, root) {
       for (p in a) {
           if (a[p]._id.toString() == parentId.toString()) {
               if (!a[p].children) {
                   a[p].children = [];
               }
               a[p].children.push(t);
           }
       }
   }

Answer 7

There is an error in your string

a[p].children.push(t);

It should be

a[p].children.push(child);

also I'm little optimize it:

var data = [{"id":1,"name":"X","parentId":null},{"id":2,"name":"Y","parentId":1},{"id":3,"name":"D","parentId":2},{"id":2,"name":"S","parentId":1},{"id":5,"name":"K","parentId":4}]
    var obj = {};
    obj.rootElements = [];
    for (i in data) {
        var _elem = data[i];
        if (_elem.parentId) {
            var _parentId = _elem.parentId;
            if (_parentId == _elem.id) {
                // check children, if false - add
                if (!_elem.children) {
                    _elem.children = [];
                }
                _elem.children.push(_elem);
            }
            else {
                addChildToParent(_elem, _parentId);
            }
        }
        else // is root
        {
            obj.rootElements.push(_elem);
        }
    }
    function addChildToParent(child, parentId, root) {
        for (j in data) {
            if (data[j].id.toString() == parentId.toString()) {
                if (!data[j].children) {
                    data[j].children = [];
                }
                data[j].children.push(child);
            }
        }
    }
    res.send(obj.rootElements);