Create a hierarchy of arrays from a flat array

Question

Consider I have an array like this

const ar = [
  {id: 1, name: "A", parent: null},
  {id: 2, name: "B", parent: 1},
  {id: 11, name: "AA", parent: 1},
  {id: 12, name: "AB", parent: 1},
  {id: 111, name: "AAA", parent: 11},
  {id: 41, name: "CC", parent: 4},
  {id: 4, name: "C", parent: 1},
];

How do I create a hierarchy of just one object like this

{
    id: 1,
    name: "A",
    parent: null,
    children: [
      {
        id: 11,
        name: "AA",
        parent: 1,
        children: [
          {id: 111, name: "AAA", parent: 11}],
      },
      {id: 2, name: "B", parent: 1, children: []},
      {
        id: 4,
        name: "C",
        parent: 1,
        children: [{id: 41, name: "CC", parent: 4, children: []}],
      },
    ],
  }

The id is actually not a number in my actual app. It's a random string BTW.

I could do it recursively by drilling through the children array but it is not the most effective way. Can somebody help please?

Are you trying to avoid a solution to go through array and then create the object in a for loop? — Shameel Uddin
– Shameel Uddin, Commented May 18, 2022 at 14:54
"The id is actually not a number in my actual app. It's a random string BTW." Please update your question to replace number id with strings to avoid confusion for people who don't read that line — Samathingamajig
– Samathingamajig, Commented May 18, 2022 at 14:54
Is it always guaranteed that there will be exactly one element with no parent? — Samathingamajig
– Samathingamajig, Commented May 18, 2022 at 14:55
Does this answer your question? Build tree array from flat array in javascript — Tomty
– Tomty, Commented May 18, 2022 at 15:10

Samathingamajig · Accepted Answer · 2022-05-18 15:06:13Z

1

const ar = [
  {id: 1, name: "A", parent: null},
  {id: 2, name: "B", parent: 1},
  {id: 11, name: "AA", parent: 1},
  {id: 12, name: "AB", parent: 1},
  {id: 111, name: "AAA", parent: 11},
  {id: 41, name: "CC", parent: 4},
  {id: 4, name: "C", parent: 1},
];

const hierarchy = (arr) => {
  const map = {};
  let root;
  for (const ele of arr) {
    map[ele.id] = ele;
    ele.children = [];
  }
  for (const ele of arr) {
    if (map[ele.parent] != undefined)
      map[ele.parent].children.push(ele);
    else
      root = ele;
  }
  return root;
}

console.log(hierarchy(ar));

edited May 18, 2022 at 15:06

answered May 18, 2022 at 15:00

Samathingamajig

13.5k3 gold badges19 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

epascarello · Accepted Answer · 2022-05-18 15:16:58Z

First step is to map the items by the id so you have an easy look up so you are not looping over the array multiple times. After that you just need to loop over and add a children array to the parent and add the reference.

const ar = [
  {id: 1, name: "A", parent: null},
  {id: 2, name: "B", parent: 1},
  {id: 11, name: "AA", parent: 1},
  {id: 12, name: "AB", parent: 1},
  {id: 111, name: "AAA", parent: 11},
  {id: 41, name: "CC", parent: 4},
  {id: 4, name: "C", parent: 1},
];

// make a look up by the id
const mapped = ar.reduce((acc, item) => {
  acc[item.id] = item;
  return acc;
}, {});

// loop over
const result = ar.reduce((acc, item) => {
  // if there there is no parent, we know it is the first so return it
  const parentId = item.parent;
  if (!parentId) return item;
  
  // if we have a parent, see if we found this yet, if not add the array
  mapped[parentId].children = mapped[parentId].children || []; 
  // set the item as a child
  mapped[parentId].children.push(item);
  
  return acc;
}, null);

console.log(result)

RenaudC5 · Accepted Answer · 2022-05-18 15:35:46Z

0

You can iterate through the array and push the elem to the right place each time.

To get the root, you can then retrieve the element without parent.

const arr = [{id: 1, name: "A", parent: null},
  {id: 2, name: "B", parent: 1},
  {id: 11, name: "AA", parent: 1},
  {id: 12, name: "AB", parent: 1},
  {id: 111, name: "AAA", parent: 11},
  {id: 41, name: "CC", parent: 4},
  {id: 4, name: "C", parent: 1}]
  
arr.forEach(elem => elem.children = [])
  
  arr.forEach(elem => {
    if(elem.parent){
      const parent = arr.find(x => x.id === elem.parent)
      if(parent)parent.children.push(elem)
    }
  })
  
  console.log(arr.find(x => !x.parent))

Note : If you want to optimize a little more, you can add the children array in the second forEach

edited May 18, 2022 at 15:35

answered May 18, 2022 at 14:59

RenaudC5

3,8591 gold badge13 silver badges32 bronze badges

2 Comments

Samathingamajig Over a year ago

Crashes when there is "an object with a parent but the parent isn't in the array"

RenaudC5 Over a year ago

Might be better now

Collectives™ on Stack Overflow

Create a hierarchy of arrays from a flat array

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related