How to create a nested array based on a plain object

Question

I have an endpoint that outputs data in the following format:

const result = [
 {id: 4, parentId: null, name: 'Fruits & Veggies'},
 {id: 12, parentId: 133, name: 'Sanguinello'},
 {id: 3, parentId: 4, name: 'Fruits'},
 {id: 67, parentId: 98, name: 'Sesame'},
 {id: 23, parentId: 3, name: 'Orange'},
 {id: 7, parentId: null, name: 'Grains'},
 {id: 134, parentId: 7, name: 'Flour'},
 {id: 3512, parentId: 23, name: 'Navel Orange'},
 {id: 98, parentId: null, name: 'Seeds'},
 {id: 4122, parentId: 58, name: 'Lamb'},
 {id: 133, parentId: 23, name: 'Blood Orange'},
];

And I need to create a recursive function to get a potentially infinitely nested object that should be formatted as follows:

const infiniteTreeOutput = {
 children: [
 { label: 'Fruits & Veggies', id: 4, children: [
 { label: 'Fruits', id: 3, children: [
 { label: 'Orange', id: 23, children: [
 { label: 'Navel Orange', id: 3512 },
 { label: 'Blood Orange', id: 133, children: [
 { label: 'Sanguinello', id: 12 }
 ]
 }
 ]
 }
 ]
 }
 ]
 },
 { label: 'Grains', id: 7 },
 { label: 'Seeds', id: 98, children: [
 { label: 'Sesame', id: 67 }
 ]
 }
 ]
};

So:

• If parentId is null those are on the top level (Fruits & Veggies, Grains, Seeds).
• If a given node does not have children then it shouldn't have that property at all.
• If there's orphaned data (like 'Lamb' here of which we don't have its parent, then we should ignore that object).

I have an awful working function but I would love to know if it would be possible to have a recursive solution.

• Nina Scholz: please add your function. why a recursive function?
• Ruud Helderman: Do you need the solution to be robust against circular parent-child relationships?
• Nicolas Kruk: @NinaScholz I'm trying to translate what I have into this invented foods model. Will try to post it asap.
• Nicolas Kruk: @ruud-helderman I don't think so. The only case I need to cover is orphaned items (objects without referenced parent in the response). Like the case of "Lamb" in my example.

Answer 1

You could take a simple single loop approach without recursion, but with an object for keeping all nodes.

const
 data = [{ id: 4, parentId: null, name: 'Fruits & Veggies' }, { id: 12, parentId: 133, name: 'Sanguinello' }, { id: 3, parentId: 4, name: 'Fruits' }, { id: 67, parentId: 98, name: 'Sesame' }, { id: 23, parentId: 3, name: 'Orange' }, { id: 7, parentId: null, name: 'Grains' }, { id: 134, parentId: 7, name: 'Flour' }, { id: 3512, parentId: 23, name: 'Navel Orange' }, { id: 98, parentId: null, name: 'Seeds' }, { id: 133, parentId: 23, name: 'Blood Orange' }],
 tree = function (data, root) {
 var t = {};
 data.forEach(({ id, parentId, name: label }) => {
 Object.assign(t[id] = t[id] || {}, { label, id });
 ((t[parentId] ??= { label: '', id: null, }).children ??= []).push(t[id]);
 });
 return t[root].children;
 }(data, null);
console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

• sarora: what is the ??= ... is that a typo?
• Nina Scholz: it wouldn't work with a typo ... ;-) --> logical nullish assignment ??=
• sarora: ah! thanks. i copy / pasted into jsbin and it wasn't recognizing it. weird.
• Mulan: This is a beautiful algorithm once you see how Nina sees it. Since you are using nullish assignment, you could use t[id] ??= {} instead of t[id] = t[id] || {}. And t[parentId] ??= { label: "", id: null } can be simplified to t[parentId] ??= {} since you only return the children property of this node. Thanks for sharing :D
• Nina Scholz: @Thankyou, you are right. the default object is just a cosmetic part to keep label and id in front of the object and children at the end.