How to create a tree (parent-child) object from Array in Javascript

Question

I have an array like

[
  "parent1|child1|subChild1",
  "parent1|child1|subChild2",
  "parent|child2|subChild1",
  "parent1|child2|subChild2",
  "parent2|child1|subChild1",
  "parent2|child1|subChild2",
  "parent2|child2|subChild1",
.
.
.    
]

Wherein my first string before | is the parent and the second string before | is the child and the third string after the second | is the subchild

How can I convert this array into an object like

[
 {
  "id": "parent1",
  "children":[
   {
    "id": "child1",
    "children":[
     {
      "id": "subChild1"
     }
    ]
   }
  ]
 }
]

Parent -> child -> subchild object

Based on Sebastian's answer I tried below using typescript

private genTree(row) {
        let self = this;
        if (!row) {
            return;
        }
        const [parent, ...children] = row.split('|');
        if (!children || children.length === 0) {
            return [{
                id: parent,
                children: []
            }];
        }
        return [{
            id: parent,
            children: self.genTree(children.join('|'))
        }];
    }

    private mergeDeep(children) {
        let self = this;
        const res = children.reduce((result, curr) => {
            const entry = curr;
            const existing = result.find((e) => e.id === entry.id);
            if (existing) {
                existing.children = [].concat(existing.children, entry.children);
            } else {
                result.push(entry);
            }
            return result;
        }, []);
        for (let i = 0; i < res.length; i++) {
            const entry = res[i];
            if (entry.children && entry.children.length > 0) {
                entry.children = self.mergeDeep(entry.children);
            }
        };
        return res;
    }

private constructTree(statKeyNames){
    let self = this;
    const res = this.mergeDeep(statKeyNames.map(self.genTree).map(([e]) => e));
    console.log(res);
}

but this gives me:

Cannot read property 'genTree' of undefined" error

Update:

As per Sebastian's comment changed self.genTree to this.genTree.bind(this) and it worked without any issues

adiga · Accepted Answer · 2019-11-07 08:52:05Z

5

You could use a mapper object which maps each object to it's unique path (You could map the object with each id, but id is not unique here). Then reduce each partial item in the array. Set the root object as the initialValue. The accumulator will be the parent object for the current item. Return the current object in each iteration.

const input = [
    "parent1|child1|subChild1",
    "parent1|child1|subChild2",
    "parent1|child2|subChild1",
    "parent1|child2|subChild2",
    "parent2|child1|subChild1",
    "parent2|child1|subChild2",
    "parent2|child2|subChild1"
  ],
  mapper = {},
  root = { children: [] }

for (const str of input) {
  let splits = str.split('|'),
      path = '';

  splits.reduce((parent, id, i) => {
    path += `${id}|`;

    if (!mapper[path]) {
      const o = { id };
      mapper[path] = o; // set the new object with unique path
      parent.children = parent.children || [];
      parent.children.push(o)
    }
    
    return mapper[path];
  }, root)
}

console.log(root.children)

edited Nov 7, 2019 at 8:52

answered Nov 7, 2019 at 8:35

adiga

35.4k9 gold badges65 silver badges88 bronze badges

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

2 Comments

Ashish Singh Over a year ago

For some reasons, this approach works better for all the scenarios and is more performant.

adiga Over a year ago

@AshishNandanSingh because there are no nested loops and find() at every level. It only depends on mapper object. Every partial path like parent1| or parent1|child1| or parent2|child2|subChild1 is added and a reference to the object is kept as value. Whenever a new child to that already mapped path comes up, we just need to access it and add it as it's child. If it doesn't exist, we add the path as key. You can inspect the mapper object to understand how it works.

Sebastian Kaczmarek · Accepted Answer · 2019-11-07 07:47:10Z

4

You have to use recursion for that. Take a look here:

const arr = [
  "parent1|child1|subChild1",
  "parent1|child1|subChild2",
  "parent|child2|subChild1",
  "parent1|child2|subChild2",
  "parent2|child1|subChild1",
  "parent2|child1|subChild2",
  "parent2|child2|subChild1"
];

function genTree(row) {

  const [parent, ...children] = row.split('|');

  if (!children || children.length === 0) {
    return [{
      id: parent,
      children: []
    }];
  }

  return [{
    id: parent,
    children: genTree(children.join('|'))
  }];
};

function mergeDeep(children) {

  const res = children.reduce((result, curr) => {

    const entry = curr;

    const existing = result.find((e) => e.id === entry.id);
    if (existing) {

      existing.children = [].concat(existing.children, entry.children);
    } else {
      result.push(entry);
    }

    return result;
  }, []);

  for (let i = 0; i < res.length; i++) {

    const entry = res[i];
    if (entry.children && entry.children.length > 0) {
      entry.children = mergeDeep(entry.children);
    }
  };

  return res;
}

const res = mergeDeep(arr.map(genTree).map(([e]) => e));
console.log(JSON.stringify(res, false, 2));

I used two helpers here: genTree(row) which recursively generates a simple tree from each row, and mergeDeep(children) which reduces the first-level trees in the result of arr.map(genTree).map(([e]) => e), and then iterates over the array and recursively does the same thing to all children of each entry.

answered Nov 7, 2019 at 7:47

Sebastian Kaczmarek

8,5254 gold badges25 silver badges44 bronze badges

8 Comments

Keshav1007 Over a year ago

I am trying to convert this into typescript.. but i am getting error that "Cannot read property 'genTree' of undefined"

Sebastian Kaczmarek Over a year ago

What was your attempt? It's hard to say without any code which produces the error

Sebastian Kaczmarek Over a year ago

Ah, you didn't define self, try doing simply this.genTree

Keshav1007 Over a year ago

I got error with "this" then i added "self". It was missed in the question, i added the self also in question now

Sebastian Kaczmarek Over a year ago

How is the constructTree(...) method being called? Could you please also post the code which calls this method?

|

Collectives™ on Stack Overflow

How to create a tree (parent-child) object from Array in Javascript

2 Answers 2

2 Comments

8 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

8 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related