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.

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.

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. — zerkms, Dec 26 '18 at 23:32

Patrick Roberts · Answer 1 · 2019-12-05T18:10:28.077

22

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.

edited Dec 05 '19 at 18:10

answered Dec 26 '18 at 23:35

Patrick Roberts

49,224
10
102
153

score 3 · Accepted Answer · answered Dec 26 '18 at 23:34

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));

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. — Patrick Roberts, Dec 26 '18 at 23:37

score 1 · Answer 3 · answered Dec 26 '18 at 23:47

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)

697 · Answer 4 · 2023-02-13T20:25:43.710

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

JavaScript Recursive Search On An Array Of Objects

4 Answers4

Linked

Related