I want to create a recursive function that receive a List of objects that contains the id and parent_id. If the parent of an element is in the list I want to remove it and add it to the parent.
Convert this:
{
"id": 180,
"children": [],
"parent_id": 195,
"name": "Object 180"
},
{
"id": 193,
"children": [],
"parent_id": 180,
"name": "Object 193"
},
{
"id": 194,
"children": [],
"parent_id": 180,
"name": "Object 194"
}
{
"id": 199,
"children": [],
"parent_id": 187,
"name": "Object 199"
}
{
"id": 304,
"children": [],
"parent_id": 193,
"name": "Object 304"
}
To this:
{
"id": 180,
"children": [
{
"id": 193,
"children": [
{
"id": 304,
"children": [],
"parent_id": 193,
"name": "Object 304"
}
],
"parent_id": 180,
"name": "Object 193"
},
{
"id": 194,
"children": [],
"parent_id": 180,
"name": "Object 194"
}
],
"parent_id": 195,
"name": "Object 180"
},
{
"id": 199,
"children": [],
"parent_id": 187,
"name": "Object 199"
}
Sometimes the parent_id is null, and there is no limit of levels of the parents.
You don't need a recursive function. Just track items you've already seen and if parent exists in it add to parent.children or add a new root node.
An example complete solution is attached.
type Item = {
id: number,
children: Item[],
parent_id: number,
name: string,
}
const items: Item[] = [
{
"id": 180,
"children": [],
"parent_id": 195,
"name": "Object 180"
},
{
"id": 193,
"children": [],
"parent_id": 180,
"name": "Object 193"
},
{
"id": 194,
"children": [],
"parent_id": 180,
"name": "Object 194"
},
{
"id": 199,
"children": [],
"parent_id": 187,
"name": "Object 199"
},
{
"id": 304,
"children": [],
"parent_id": 193,
"name": "Object 304"
}
];
function nest(items:Item[]): Item[] {
const output: Item[] = [];
const idToItem = new Map<number,Item>();
for (let item of items) {
// Either add to parent. Or create a new root level node
if (idToItem.has(item.parent_id)) {
idToItem.get(item.parent_id)!.children.push(item);
} else {
idToItem.set(item.id, item);
output.push(item);
}
}
return output;
}
console.log(nest(items));
Since basarat's answer does not account for items nested more than one level.
Here a solution that creates an output with arbitrary nesting-depth:
const listToTree = (input) => {
const map = new Map(input.map((item) => [item.id, item]));
const output = [];
for (const item of input) {
if (map.has(item.parent_id)) {
map.get(item.parent_id).children.push(map.get(item.id));
} else {
output.push(map.get(item.id));
}
}
return output;
};
const input = [
{
"id": 180,
"value": 10,
"children": [],
"parent_id": 195,
"name": "Object 180"
},
{
"id": 193,
"value": 10,
"children": [],
"parent_id": 180,
"name": "Object 193"
},
{
"id": 194,
"value": 10,
"children": [],
"parent_id": 180,
"name": "Object 194"
},
{
"id": 199,
"children": [],
"parent_id": 187,
"name": "Object 199"
},
{
"id": 304,
"value": 10,
"children": [],
"parent_id": 193,
"name": "Object 304"
},
{
"id": 305,
"value": 10,
"children": [],
"parent_id": 194,
"name": "Object 304"
}
];
const output = listToTree(input);
console.log(output);If you want to aggregate values along ancestry chains of the resulting tree I would recommend to do this in a separate function afterwards. This will keep your code cleaner, easier to test and more readable.
The implementation depends on whether or not your input-array is sorted (children before parents). If you want to process unordered inputs you have to loop through the each ancestry chain.
function aggregateValue(branch) {
const children = branch.children || [];
return children.reduce((sum, child) => sum + aggregateValue(child), branch.value || 0);
}
function aggregateValueAlongBranches(tree) {
return tree.map((branch) => {
return {
...branch,
aggregatedValue: aggregateValue(branch),
children: aggregateValueAlongBranches(branch.children),
};
});
}
const input = [
{
"id": 180,
"value": 10,
"children": [
{
"id": 193,
"value": 10,
"children": [
{
"id": 304,
"value": 10,
"children": [],
"parent_id": 193,
"name": "Object 304"
}
],
"parent_id": 180,
"name": "Object 193"
},
{
"id": 194,
"value": 10,
"children": [
{
"id": 305,
"value": 10,
"children": [],
"parent_id": 194,
"name": "Object 304"
}
],
"parent_id": 180,
"name": "Object 194"
}
],
"parent_id": 195,
"name": "Object 180"
},
{
"id": 199,
"children": [],
"parent_id": 187,
"name": "Object 199"
}
];
const output = aggregateValueAlongBranches(input);
console.log(output);