JavaScript Recursive Search On An Array Of Objects

Question

I have an array of objects that have deeply nested children and sometimes children within children. I am attempting to handle this recursively, but I am getting stuck.

The goal of the function is to return a single data object that matches the id.

My Data looks like this:

data: [
 {
 id: 'RAKUFNUBNY00UBZ40950',
 name: 'Grade 1 Cover',
 activityId: 'RAKUFNUBNY00UBZ40950',
 nodeType: 'activity',
 suppressed: false,
 hidden: false
 },
 {
 children: [
 {
 id: 'SLWDYEQHTZAFA3ALH195',
 name: 'Build Background Video',
 activityId: 'SLWDYEQHTZAFA3ALH195',
 nodeType: 'activity',
 suppressed: false,
 hidden: false,
 assetReference: {
 referenceId: 'UWFHA5A1E0EGKCM0W899',
 assetType: 'image'
 }
 },
 {
 children: [
 {
 id: 'HQUCD2SSRKMYC2PJM636',
 name: 'Eat or Be Eaten Splash Card',
 activityId: 'HQUCD2SSRKMYC2PJM636',
 nodeType: 'activity',
 suppressed: false,
 hidden: true
 },
 {
 children: [
 {
 id: 'ZDTWEZFL13L8516VY480',
 name: 'Interactive Work Text: Eat or Be Eaten',
 activityId: 'ZDTWEZFL13L8516VY480',
 nodeType: 'activity',
 suppressed: false,
 hidden: true,
 defaultLaunchMode: 'modal'
 }
 ],

My attempt at solving this is like this:

findNode(id, currentNode) {
 console.log('id', id);
 console.log('findNode', currentNode);
 var i, currentChild, result, counter;
 counter = 0;
 console.log('first conditional statement', currentNode);
 if (id && currentNode.id === id) {
 return currentNode[0];
 } else {
 counter++;
 // Use a for loop instead of forEach to avoid nested functions
 // Otherwise "return" will not work properly
 console.log('counter', counter);
 console.log('currentNode', currentNode[counter]);
 console.log('currentNode Children', currentNode.children);
 for (i = counter; i < currentNode.children.length; i += 1) {
 console.log(currentNode[i].children[i]);
 currentChild = currentNode[i].children[i];
 // Search in the current child
 result = this.findNode(id, currentChild);
 // Return the result if the node has been found
 if (result !== false) {
 return result;
 }
 }
 // The node has not been found and we have no more options
 return false;
 }
 }

The code above fails because I having an extremely difficult time keeping track of a counter to loop through everything. enter image description here

I also added a sample picture of my data output to give you a better example of how my data is structured. Any help will be greatly appreciated.

• zerkms: Make up a simpler recursive structure and learn how to iterate through it first. Sometimes doing the job on real life data structures does not work, so it's fine to simplify for learning purposes.

Answer 1

You shouldn't need a counter to locate a single node with a matching id. Try this simpler approach:

function findNode (id, array) {
 for (const node of array) {
 if (node.id === id) return node;
 if (node.children) {
 const child = findNode(id, node.children);
 if (child) return child;
 }
 }
}

It will return undefined if there is no match.

Answer 2

To avoid the need for manual iteration, you might consider using an array method like reduce instead - return the accumulator if it's truthy (that is, an object was found already), or return the object being iterated over if the ID matches, or recursively iterate over the object's children to find a match.

const data=[{id:'RAKUFNUBNY00UBZ40950',name:'Grade 1 Cover',activityId:'RAKUFNUBNY00UBZ40950',nodeType:'activity',suppressed:!1,hidden:!1},{children:[{id:'SLWDYEQHTZAFA3ALH195',name:'Build Background Video',activityId:'SLWDYEQHTZAFA3ALH195',nodeType:'activity',suppressed:!1,hidden:!1,assetReference:{referenceId:'UWFHA5A1E0EGKCM0W899',assetType:'image'}},{children:[{id:'HQUCD2SSRKMYC2PJM636',name:'Eat or Be Eaten Splash Card',activityId:'HQUCD2SSRKMYC2PJM636',nodeType:'activity',suppressed:!1,hidden:!0},{children:[{id:'ZDTWEZFL13L8516VY480',name:'Interactive Work Text: Eat or Be Eaten',activityId:'ZDTWEZFL13L8516VY480',nodeType:'activity',suppressed:!1,hidden:!0,defaultLaunchMode:'modal'}],}],}],}]
function findId(id, arr) {
 return arr.reduce((a, item) => {
 if (a) return a;
 if (item.id === id) return item;
 if (item.children) return findId(id, item.children);
 }, null);
}
console.log(findId('HQUCD2SSRKMYC2PJM636', data));

• Patrick Roberts: The downside of reduce() is you're forced to iterate to the end of each array at each level of recursion. A simple for loop does not have that limitation.

Answer 3

If your ids are unique and finding an object by id is a common task, you might want to consider creating a lookup object to improve performance. Creating the lookup object is an O(n) task; afterwards, looking up an object by id is O(1).

const data = [ { id: 'RAKUFNUBNY00UBZ40950', name: 'Grade 1 Cover', activityId: 'RAKUFNUBNY00UBZ40950', nodeType: 'activity', suppressed: false, hidden: false }, { children: [ { id: 'SLWDYEQHTZAFA3ALH195', name: 'Build Background Video', activityId: 'SLWDYEQHTZAFA3ALH195', nodeType: 'activity', suppressed: false, hidden: false, assetReference: { referenceId: 'UWFHA5A1E0EGKCM0W899', assetType: 'image' } }, { children: [ { id: 'HQUCD2SSRKMYC2PJM636', name: 'Eat or Be Eaten Splash Card', activityId: 'HQUCD2SSRKMYC2PJM636', nodeType: 'activity', suppressed: false, hidden: true }, { children: [ { id: 'ZDTWEZFL13L8516VY480', name: 'Interactive Work Text: Eat or Be Eaten', activityId: 'ZDTWEZFL13L8516VY480', nodeType: 'activity', suppressed: false, hidden: true, defaultLaunchMode: 'modal' } ] } ] } ] } ];
const lookup = {};
const registerIds = a => {
 a.forEach(o => {
 if ('id' in o) {
 lookup[o.id] = o;
 } else if ('children' in o) {
 registerIds(o.children)
 }
 });
}
registerIds(data);
console.log(lookup)

Answer 4

Sorry for my two cents, just want to add a universal method that includes nested arrays

const cars = [{
 id: 1,
 name: 'toyota',
 subs: [{
 id: 43,
 name: 'supra'
 }, {
 id: 44,
 name: 'prius'
 }]
}, {
 id: 2,
 name: 'Jeep',
 subs: [{
 id: 30,
 name: 'wranger'
 }, {
 id: 31,
 name: 'sahara'
 }]
}]
function searchObjectArray(arr, key, value) {
 let result = [];
 
 arr.forEach((obj) => {
 if (obj[key] === value) {
 result.push(obj);
 } else if (obj.subs) {
 result = result.concat(searchObjectArray(obj.subs, key, value));
 }
 });
 console.log(result)
 return result;
}
searchObjectArray(cars, 'id', '31') 
searchObjectArray(cars, 'name', 'Jeep')

I hope this helps someone