So I have a multiple array of object and each object my contain a child.
e.g
const data = [
{
id: 1,
name: 'parent 1',
children: [
{
id: 'c1',
name: 'child 1',
children: [
{
id: 'g1',
name: 'grand 1',
children: [],
},
],
},
],
},
{
id: 2,
name: 'parent 2',
children: [
{
id: 2,
name: 'c1',
children: [],
},
],
},
{ id: 3, name: 'parent 3', children: [] },
];
what I wanted to happen is that if the Id that I'm searching for is 'g1', I would get the result
const result = ['parent 1', 'c1', 'grand 1']
the loop would only stop and get all the names that it went thru until the condition, in this case the id, is met
current approach done
/**
* Details
* @param id the value you are searching for
* @param items nested array of object that has child
* @param key name of the value you are looking for
* @returns string of array that matches the id
* @example ['parent 1', 'c1', 'grand 1']
*/
export function findAll(id: string, items: any, key: string): string[] {
let i = 0;
let found;
let result = [];
for (; i < items.length; i++) {
if (items[i].id === id) {
result.push(items[i][key]);
} else if (_.isArray(items[i].children)) {
found = findAll(id, items[i].children, key);
if (found.length) {
result = result.concat(found);
}
}
}
return result;
}
So I have a multiple array of object and each object my contain a child.
e.g
const data = [
{
id: 1,
name: 'parent 1',
children: [
{
id: 'c1',
name: 'child 1',
children: [
{
id: 'g1',
name: 'grand 1',
children: [],
},
],
},
],
},
{
id: 2,
name: 'parent 2',
children: [
{
id: 2,
name: 'c1',
children: [],
},
],
},
{ id: 3, name: 'parent 3', children: [] },
];
what I wanted to happen is that if the Id that I'm searching for is 'g1', I would get the result
const result = ['parent 1', 'c1', 'grand 1']
the loop would only stop and get all the names that it went thru until the condition, in this case the id, is met
current approach done
/**
* Details
* @param id the value you are searching for
* @param items nested array of object that has child
* @param key name of the value you are looking for
* @returns string of array that matches the id
* @example ['parent 1', 'c1', 'grand 1']
*/
export function findAll(id: string, items: any, key: string): string[] {
let i = 0;
let found;
let result = [];
for (; i < items.length; i++) {
if (items[i].id === id) {
result.push(items[i][key]);
} else if (_.isArray(items[i].children)) {
found = findAll(id, items[i].children, key);
if (found.length) {
result = result.concat(found);
}
}
}
return result;
}
-
What have you tried? Also,
const result = 'parent 1' > 'c1' > 'grand 1'this is invalid data object, you may verify what data structure do you want. – ikhvjs Commented Aug 27, 2021 at 14:33 - @ikhvjs, I updated the result that I wanted to see, thanks for the ment – noxin D invictus Commented Aug 27, 2021 at 14:35
- What have you tried so far? I think a recursive function approach would be good for your case. – ikhvjs Commented Aug 27, 2021 at 14:38
- @ikhvjs, I tried this one, 3rd answer, stackoverflow./questions/30714938/… with some modifications but I can't seem to find a way to store the name of the parents on result array – noxin D invictus Commented Aug 27, 2021 at 14:45
- Can you please show us your approach? – ikhvjs Commented Aug 27, 2021 at 14:50
7 Answers
Reset to default 3I wrote this iterative piece of code that may help you. It basically traverses the structure storing the path from the top-level until the desired id:
function getPath(obj, id) {
// We need to store path
// Start stack with root nodes
let stack = obj.map(item => ({path: [item.name], currObj: item}));
while (stack.length) {
const {path, currObj} = stack.pop()
if (currObj.id === id) {
return path;
} else if (currObj.children?.length) {
stack = stack.concat(currObj.children.map(item => ({path: path.concat(item.name), currObj: item})));
}
}
return null; // if id does not exists
}
This code assumes that your structure is correct and not missing any part (except for children that can be null).
Btw, is your answer correct? I guess the path should be:
["parent 1", "child 1", "grand 1"]
The solution below is a recursive function that does the search.
const data = [
{
id: 1,
name: 'parent 1',
children: [
{
id: 'c1',
name: 'child 1',
children: [
{
id: 'g1',
name: 'grand 1',
children: [],
},
],
},
],
},
{
id: 2,
name: 'parent 2',
children: [
{
id: 2,
name: 'c1',
},
],
},
{ id: 3, name: 'parent 3', children: [{}] },
];
function getPath(object, search) {
if (object.id === search) return [object.name];
else if ((object.children) || Array.isArray(object)) {
let children = Array.isArray(object) ? object : object.children;
for (let child of children) {
let result = getPath(child, search);
if (result) {
if (object.id )result.unshift(object.name);
return result;
}
}
}
}
//const result = ['parent 1', 'c1', 'grand 1']
const result = getPath(data, 'g1');
console.log(result);You can program a recursive function where you traverse your array at the time you accumulate the objects you traverse in a stack. Once you get an object with the id you want (id == g1) you print the solution. It could be something like this:
'use strict';
function print(stack) {
//console.log("Printing result...\n");
let result = "";
stack.forEach(element => {
result += element["name"] + " > ";
});
console.log(result + "\n");
}
function walkThrough(data, id, stack) {
if (data !== undefined)
for (let i = 0; i < data.length; i++) {
const element = data[i];
//console.log("Going through " + element["name"] + " with id == " + element["id"]);
stack.push(element);
if (element["id"] == id) print(stack);
else walkThrough(element["children"], id, stack);
}
}
const data = [
{
"id": 1,
"name": 'parent 1',
"children": [
{
"id": 'c1',
"name": 'child 1',
"children": [
{
"id": 'g1',
"name": 'grand 1',
"children": [],
},
],
},
],
},
{
"id": 2,
"name": 'parent 2',
"children": [
{
"id": 2,
"name": 'c1',
},
],
},
{ "id": 3, "name": 'parent 3', "children": [{}] },
];
//Calling the function to walk through the array...
walkThrough(data, 'g1', []);
Another aproach (not so elegant as above solutions, but it works also)
Very straight forward:
Iterating with for loop down to 3rd level, and when grandchild found in 3rd level, break to escape all 3 levels.
I am curious about how the different solutions would pare performance-wise for a large dataset (let's say a million records).
let i=0, k=0, l=0;
let childrenLength = 0, grandChildrenLength = 0;
let result = [];
let foundGrandChild = false;
function searchGrandChild(searchString) {
for (i; i< data.length; ++i) {
if(data.length > 0){
childrenLength = data[i].children.length;
if(childrenLength > 0) {
for (k; k < childrenLength; ++k) {
if(data[i].children[k] != undefined) {
grandChildrenLength = data[i].children[k].children.length;
if(grandChildrenLength > 0) {
for (l; l < grandChildrenLength; ++l) {
if(data[i].children[k].children[l] != undefined) {
if(data[i].children[k].children[l].id === searchString) {
result.push(data[i].name);
result.push(data[i].children[k].id);
result.push(data[i].children[k].children[l].name);
foundGrandChild = true;
console.log('Yap, we found your grandchild