2

Sorry for the confusing title... I don't know a better summery.

I have an Array of Objects. Some of these Objects have a reference to it's parent Object. Something like that:

data: 
[
  {id: 2, parent: 1},
  {id: 1},
  {id: 3, parent: 1},
  {id: 5, parent: 3},
  {id: 4, parent: 3},
  {id: 6, parent: 2} 

]

What I want to do, is creating an Object out of this Array where the child objects are nested inside their parents. Like that:

data: {
  id: 1,
  children: [
    {
      id:2,
      children: [
        {id: 6}
      ]
    },
    {
      id:3,
      children: [
        {id: 4},
        {id: 5}
      ]
    }
  ]
}

Does anyone know a smart way of doing this? I know I have to itterate through every Object of this Array and check if there is a parent. But how can I actually create this Object?

1 Answer 1

2

Not sure it's the best way to do it, but at least it's one way to do it.

  1. First loop over the nodes:
    • Put the nodes in a lookup table by their id (nodes).
    • Find the root node (the single node with no parent).
  2. Second loop (with the lookup table complete):
    • Check if the node has a parent (true for every node except the root).
    • Get the parent node by looking up the id in the lookup table.
    • Get the parent.children array, or create it if it doesn't exist yet.
    • Add this node to that array.
    • Remove the parent property of this node.

Note that this changes the original node objects in your data object. This is intentional, since the tree is built by storing references to other nodes in parent nodes. If you need to keep the original nodes in data intact, you should clone the node objects while building the lookup table. For example, you could add node = $.extend({}, node); as first line in the lookup forEach loop (when using jQuery).

Here's an implementation and a demonstration:

var data = [
  {id: 2, parent: 1},
  {id: 1},
  {id: 3, parent: 1},
  {id: 5, parent: 3},
  {id: 4, parent: 3},
  {id: 6, parent: 2}
];

// Node lookup table
var nodes = {};
// Root node
var root = null;
// Fill lookup table and find root
data.forEach(function(node) {
    nodes[node.id] = node;
    // Assuming only one root node
    if(!("parent" in node)) {
        root = node;
    }
});
// Build tree
for(var id in nodes) {
    var node = nodes[id];
    if("parent" in node) {
        // Add to children of parent
        var parent = nodes[node.parent];
        (parent.children = parent.children || []).push(node);
        // Remove parent property (optional)
        delete node.parent;
    }
}
console.log(JSON.stringify(root));

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.