I have a JS array that looks like this:
const arr = [
{
i: "tooltip_119",
children: [
{
i: "text_345",
children: []
},
{
i: "wraper_375",
children: [
{
i: "grid_15",
children: []
}
]
}
]
},
{
i: "chart_123",
children: []
},
{
i: "graph_467",
children: []
},
]
The idea is that such an array can potentially have an infinite number of nestings. And I need a function that, taking the i parameter of some element, will return the i parameter of its parent (or 0 if the element is at the root and has no parents). An example of how such a function works:
console.log(findParent(arr, "grid_15")) // returns "wraper_375"
I wrote a function like this:
export function findParent(arr, i) { // this func has a bug on deep levels
for (let j = 0; j < arr.length; j++) {
const element = arr[j];
if (element.children && element.children.length > 0) {
const childElement = element.children.find((e) => e.i === i);
if (childElement) {
return element.i;
} else {
const parentElement = findParent(element.children, i);
if (parentElement) {
return parentElement.i;
}
}
}
}
return 0;
}
The problem is that my function doesn't work at deeper levels of nesting. I would be grateful for help
Expected outputs:
findParent(arr, "tooltip_119") // 0
findParent(arr, "chart_123") // 0
findParent(arr, "graph_467") // 0
// 0 is returned because these elems do not have parent elem
findParent(arr, "text_345") // "tooltip_119"
findParent(arr, "wraper_375") // "tooltip_119"
findParent(arr, "grid_15") // "wraper_375"
A simple recursion could be like that:
function findParent(arr, id, parentId = 0) {
for (const {children, i} of arr) {
if (i === id){
return parentId;
}
if (children.length) {
const childId = findParent(children, id, i);
if (childId !== null){
return childId;
}
}
}
if (parentId === 0) {
return parentId;
}
return null;
}
['wrong_id', 'tooltip_119', 'wraper_375', 'grid_15', 'second_childs_child', 'graph_467']
.forEach(id => console.log(id, '=>', findParent(arr, id)));<script>
const arr = [
{
i: "tooltip_119",
children: [
{
i: "text_345",
children: []
},
{
i: "wraper_375",
children: [
{
i: "grid_15",
children: []
}
]
}
]
},
{
i: "chart_123",
children: [{i: 'second_childs_child', children: []}]
},
{
i: "graph_467",
children: []
},
]
</script>Another option would be to use a stack to traverse the object:
const findParentId = (arr, id) => {
let curr = {parentId: 0, arr, j:0};
stack: while (curr) {
let { parentId, arr, j } = curr;
while (j < arr.length) {
const { children, i } = arr[j];
curr.j = ++j;
if (i === id) {
return parentId;
}
if (children.length) {
curr = { parentId: i, arr: children, j: 0, parent: curr };
continue stack;
}
}
curr = curr.parent;
}
};
['wrong_id', 'tooltip_119', 'wraper_375', 'grid_15', 'second_childs_child', 'graph_467']
.forEach(id => console.log(id, '=>', findParentId(arr, id)));<script>
const arr=[{i:"tooltip_119",children:[{i:"text_345",children:[]},{i:"wraper_375",children:[{i:"grid_15",children:[]}]}]},{i:"chart_123",children:[{i:"second_childs_child",children:[]}]},{i:"graph_467",children:[]},];
</script>And benchmarking:
` Chrome/121
----------------------------------------------------------------------------
> n=3 | n=30 | n=300 | n=3000
recursion 1.00x x1m 94 | 1.00x x1m 271 | 1.00x x100k 197 | 1.00x x10k 195
stack 1.41x x1m 133 | 1.42x x1m 385 | 1.39x x100k 274 | 1.34x x10k 262
----------------------------------------------------------------------------
https://github.com/silentmantra/benchmark `
const $chunk=[{i:"tooltip_119",children:[{i:"text_345",children:[]},{i:"wraper_375",children:[{i:"grid_15",children:[]}]}]},{i:"chart_123",children:[{i:"second_childs_child",children:[]}]},{i:"graph_467",children:[]},];
const $input = [];
const arr = $input;
const ids = ['wrong_id', 'tooltip_119', 'wraper_375', 'grid_15', 'second_childs_child', 'graph_467'];
// @benchmark recursion
const findParentId = (arr, id, parentId = 0) => {
for(const {children, i} of arr){
if(i === id){
return parentId;
}
if(children.length){
const childId = findParentId(children, id, i);
if(childId){
return childId;
}
}
}
};
// @run
ids.map(id => findParentId(arr, id));
// @benchmark stack
const findParentId2 = (arr, id) => {
let curr = {parentId: 0, arr, j:0};
stack: while (curr) {
let { parentId, arr, j } = curr;
while (j < arr.length) {
const { children, i } = arr[j];
curr.j = ++j;
if (i === id) {
return parentId;
}
if (children.length) {
curr = { parentId: i, arr: children, j: 0, parent: curr };
continue stack;
}
}
curr = curr.parent;
}
};
// @run
ids.map(id => findParentId2(arr, id));
/*@end*/eval(atob('e2xldCBlPWRvY3VtZW50LmJvZHkucXVlcnlTZWxlY3Rvcigic2NyaXB0Iik7aWYoIWUubWF0Y2hlcygiW2JlbmNobWFya10iKSl7bGV0IHQ9ZG9jdW1lbnQuY3JlYXRlRWxlbWVudCgic2NyaXB0Iik7dC5zcmM9Imh0dHBzOi8vY2RuLmpzZGVsaXZyLm5ldC9naC9zaWxlbnRtYW50cmEvYmVuY2htYXJrL2xvYWRlci5qcyIsdC5kZWZlcj0hMCxkb2N1bWVudC5oZWFkLmFwcGVuZENoaWxkKHQpfX0='));