1

Similar question was asked previously here and here, there are npm-packages as well BUT - I am not able to find a JavaScript code snippet or npm package which would allow preserving the the order of the children

Consider following data structure:

var nodes = [{id: 'a', parent: null, children: ['c', 'b']},
             {id: 'b', parent: 'a', children: []},
             {id: 'c', parent: 'a', children: []}]

I would like to get a nested object like this:

var tree = {id: 'a', parent: null, children: [
    {id: 'c', parent: 'a', children: []},
    {id: 'b', parent: 'a', children: []}
]}

The important fact is, that since the order of the children of a is c, b, the resulting children array in the nested structure will preserve the order.

karlitos
  • 1,604
  • 3
  • 27
  • 59

1 Answers1

2

Quite simple if you build up a Map first:

 const nodeById = new Map(nodes.map(el => [el.id, el]));

Then you can easily build up the tree:

 let root;

 for(const node of nodes) {
   node.children = node.children.map(id => nodeById.get(id));
   if(!node.parent) root = node;
 }
Jonas Wilms
  • 132,000
  • 20
  • 149
  • 151
  • Thank you for your suggestion. I had to notice, that this approach mutates the original structure. This is very unfortunate if you work on e.g. a property of a React state object. Is there a possibility to modify your code without the necessity of deep-cloning the original structure or adding additional computational complexity ? – karlitos Sep 29 '18 at 22:35
  • @karlitos you would ha e to clone before `nodes = nodes.map(n => {...n})`, bit as you mentioned React: Only one version should actually go into the state, changing the states structure is bad – Jonas Wilms Sep 29 '18 at 22:40
  • I did not want to change the Reacts state like this. My goal was to compute derived value based on the state. I will deep-copy the original nodes array to prevent mutating the state. Still, I wonder if there is an more efficient way altogether. – karlitos Sep 30 '18 at 08:35
  • @karlitos not really, this is still O(n) – Jonas Wilms Sep 30 '18 at 09:15