Nest flat objects based on a parentId and id property

user_1183075 0
Viewed 220

Given a flat level array of objects, what's the most efficient and modern way to nest them based on a parent and id property? The top level objects have no parentId, and there's no limit to nest levels.

[{
  id: 'OS:MacOS',
  type: 'OS',
  value: 'MacOS'
}, {
  parentId: 'OS:MacOS',
  id: 'Version:Catalina',
  type: 'Version',
  value: 'Catalina'
}, {
  parentId: 'Version:Catalina',
  id: 'Browser:Chrome',
  type: 'Browser',
  value: 'Chrome'
}, {
  id: 'OS:Windows',
  type: 'OS',
  value: 'Windows'
}, {
  parentId: 'OS:Windows',
  id: 'Version:7',
  type: 'Version',
  value: '7'
}, {
  parentId: 'OS:MacOS',
  id: 'Version:Mojave',
  type: 'Version',
  value: 'Mojave'
}, {
  parentId: 'Version:Mojave',
  id: 'Browser:Chrome',
  type: 'Browser',
  value: 'Chrome'
}, {
  parentId: 'OS:Windows',
  id: 'Version:XP',
  type: 'Version',
  value: 'XP'
}, {
  parentId: 'Version:XP',
  id: 'Browser:Chrome',
  type: 'Browser',
  value: 'Chrome'
}]

Where parentId matches up to a corresponding id field. Ideally transforming them to include a children array field along the lines of:

[{
  id: 'OS:MacOS',
  type: 'OS',
  value: 'MacOS',
  children: [
    {
      parentId: 'OS:MacOS',
      id: 'Version:Catalina',
      type: 'Version',
      value: 'Catalina',
      children: [
        {
          parentId: 'Version:Catalina',
          id: 'Browser:Chrome',
          type: 'Browser',
          value: 'Chrome'
        }
      ]
    },
    {
      parentId: 'OS:MacOS',
      id: 'Version:Mojave',
      type: 'Version',
      value: 'Mojave',
      children: [
        {
          parentId: 'Version:Mojave',
          id: 'Browser:Chrome',
          type: 'Browser',
          value: 'Chrome'
        }
      ]
    }
  ]
}, {
  id: 'OS:Windows',
  type: 'OS',
  value: 'Windows',
  children: [
    {
      parentId: 'OS:Windows',
      id: 'Version:7',
      type: 'Version',
      value: '7'
    },
    {
      parentId: 'OS:Windows',
      id: 'Version:XP',
      type: 'Version',
      value: 'XP',
      children: [
        {
          parentId: 'Version:XP',
          id: 'Browser:Chrome',
          type: 'Browser',
          value: 'Chrome'
        }
      ]
    }
  ]
}]

Thoughts appreciated!

object nested arrays javascript
2 Answers

You could use reduce in recursive function that will pass down the current element id and compare it with parent id in nested calls.

const data = [{"id":"OS:MacOS","type":"OS","value":"MacOS"},{"parentId":"OS:MacOS","id":"Version:Catalina","type":"Version","value":"Catalina"},{"parentId":"Version:Catalina","id":"Browser:Chrome","type":"Browser","value":"Chrome"},{"id":"OS:Windows","type":"OS","value":"Windows"},{"parentId":"OS:Windows","id":"Version:7","type":"Version","value":"7"},{"parentId":"OS:MacOS","id":"Version:Mojave","type":"Version","value":"Mojave"},{"parentId":"Version:Mojave","id":"Browser:Chrome","type":"Browser","value":"Chrome"},{"parentId":"OS:Windows","id":"Version:XP","type":"Version","value":"XP"},{"parentId":"Version:XP","id":"Browser:Chrome","type":"Browser","value":"Chrome"}]

function nested(data, pid = undefined) {
  return data.reduce((r, e) => {
    if (e.parentId == pid) {
      const obj = { ...e }
      const children = nested(data, e.id);
      if (children.length) obj.children = children;
      r.push(obj)
    }

    return r;
  }, [])
}

const result = nested(data);
console.log(result)

user_46207710

The reducer approach by Nenad works, but is pretty inefficient as it iterates through the data list n^2 times. Here is an O(n) solution:

function buildTree(data) {
    const store = new Map(); // stores data indexed by it's id
    const rels = new Map(); // stores array of children associated with id
    const roots = []; // stores root nodes
    data.forEach(d => {
        store.set(d.id, d);
        !rels.get(d.id) ? rels.set(d.id, []) : undefined; // noOp.;
        if (!d.parentId) {
            roots.push(d.id)
            return;
        }
        const parent = rels.get(d.parentId) || [];
        parent.push(d.id);
        rels.set(d.parentId, parent);
    });

    function build(id) {
        const data = store.get(id);
        const children = rels.get(id);
        if (children.length === 0) {
            return {...data}
        }
        return {...data, children: children.map(c => build(c)) };
    }

    return roots.map(r => build(r));
}

const data = [{"id":"OS:MacOS","type":"OS","value":"MacOS"},{"parentId":"OS:MacOS","id":"Version:Catalina","type":"Version","value":"Catalina"},{"parentId":"Version:Catalina","id":"Browser:Chrome","type":"Browser","value":"Chrome"},{"id":"OS:Windows","type":"OS","value":"Windows"},{"parentId":"OS:Windows","id":"Version:7","type":"Version","value":"7"},{"parentId":"OS:MacOS","id":"Version:Mojave","type":"Version","value":"Mojave"},{"parentId":"Version:Mojave","id":"Browser:Chrome","type":"Browser","value":"Chrome"},{"parentId":"OS:Windows","id":"Version:XP","type":"Version","value":"XP"},{"parentId":"Version:XP","id":"Browser:Chrome","type":"Browser","value":"Chrome"}]

console.log(JSON.stringify(buildTree(data), null, 2))

Edit Note:

Earlier answer was class based. Removed that for simplicity. You can further optimize the space storage by changing store to be index based.

user_35548760
Related