Finding value in deep nested array of object, recursively, javascript

Question

I have an array of nested objects, having parent-child relationship:

  [  
   {  
      "id":"5b9ce8d51dbb85944baddfa5",
      "name":"EARBANG",
      "parent_id":0,
      "status":"Inactive",
      "children":[  
         {  
            "id":"5b9ce8d5d978f75e4b1584ba",
            "name":"DIGINETIC",
            "parent_id":"5b9ce8d51dbb85944baddfa5",
            "status":"Active",
            "children":[  
               {  
                  "id":"5b9ce8d5cb79d63c8b38018c",
                  "name":"PREMIANT",
                  "parent_id":"5b9ce8d5d978f75e4b1584ba",
                  "status":"Active",
               }
            ]
         }
      ]
   },
   {  
      "id":"5b9ce8d51650fac75fa359c8",
      "name":"GEEKOLOGY",
      "parent_id":0,
      "status":"Active",
   },
   {  
      "id":"5b9ce8d59f52e801a2e40a97",
      "name":"TOYLETRY",
      "parent_id":0,
      "status":"Inactive",
   },
   {  
      "id":"5b9ce8d5d136fcfed2f3e0dd",
      "name":"PAPRIKUT",
      "parent_id":0,
      "status":"Inactive",
   },
   {  
      "id":"5b9ce8d53afb7a61e188c48e",
      "name":"EYERIS",
      "parent_id":0,
      "status":"Inactive",
   }
]

here I want that :

1- Find an object having id e.g. 5b9ce8d51dbb85944baddfa5

2- iterate in that objects children array (if non empty) recursively and get id of all its childrends and grand-childrens and great-grand-childrens in an array.

So my result will be like

{
    "id":"5b9ce8d51dbb85944baddfa5",
    childs: ["5b9ce8d5d978f75e4b1584ba", "5b9ce8d5cb79d63c8b38018c", ...]
}

I tried some solutions available on stack overflow, but could not get it to work.

I appreciate if anyone can help me, my DS not that strong.

Thanks

vijayst · Accepted Answer · 2018-09-22 05:59:50Z

3

Here is a search recursive function:

function searchRecursive(data, id) {
  let found = data.find(d => d.id === id);
  if (!found) {
    let i = 0;
    while(!found && i < data.length) {
      if (data[i].children && data[i].children.length) {
        found = searchRecursive(data[i].children, id);
      }
      i++;
    }
  }
  return found;
}

edited Sep 22, 2018 at 5:59

answered Sep 22, 2018 at 5:47

vijayst

22.1k18 gold badges73 silver badges113 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Shubham Gupta · Accepted Answer · 2018-09-22 06:01:17Z

2

Take a look at the code sandbox that I have created which recursively searches for id. Once id is found it calls another recursion to generate child's array.

console.log(findId(data, "5b9ce8d51dbb85944baddfa5"));
console.log(findId(data, "5b9ce8d5cb79d63c8b38018c"));

Following is the output for above two.

https://codesandbox.io/s/m4vowz8qp8

answered Sep 22, 2018 at 6:01

Shubham Gupta

2,6461 gold badge10 silver badges19 bronze badges

Comments

Adrian Brand · Accepted Answer · 2018-09-22 05:20:01Z

2

Recursively search for the id.

const data = [  
   {  
      "id":"5b9ce8d51dbb85944baddfa5",
      "name":"EARBANG",
      "parent_id":0,
      "status":"Inactive",
      "children":[  
         {  
            "id":"5b9ce8d5d978f75e4b1584ba",
            "name":"DIGINETIC",
            "parent_id":"5b9ce8d51dbb85944baddfa5",
            "status":"Active",
            "children":[  
               {  
                  "id":"5b9ce8d5cb79d63c8b38018c",
                  "name":"PREMIANT",
                  "parent_id":"5b9ce8d5d978f75e4b1584ba",
                  "status":"Active",
               }
            ]
         }
      ]
   },
   {  
      "id":"5b9ce8d51650fac75fa359c8",
      "name":"GEEKOLOGY",
      "parent_id":0,
      "status":"Active",
   },
   {  
      "id":"5b9ce8d59f52e801a2e40a97",
      "name":"TOYLETRY",
      "parent_id":0,
      "status":"Inactive",
   },
   {  
      "id":"5b9ce8d5d136fcfed2f3e0dd",
      "name":"PAPRIKUT",
      "parent_id":0,
      "status":"Inactive",
   },
   {  
      "id":"5b9ce8d53afb7a61e188c48e",
      "name":"EYERIS",
      "parent_id":0,
      "status":"Inactive",
   }
];


const search = (data, id) => data.find(d => d.id === id) || search(d.children);

console.log(search(data, '5b9ce8d51dbb85944baddfa5'));

answered Sep 22, 2018 at 5:20

Adrian Brand

21.8k4 gold badges46 silver badges67 bronze badges

2 Comments

Mark Over a year ago

This works okay for the first level, but try searching for a child (like 5b9ce8d5cb79d63c8b38018c) with it.

raju Over a year ago

Also the search value can be nth level deep.

Mark · Accepted Answer · 2018-09-22 05:52:55Z

You can find the object with a fairly standard recursive approach. The edge condition is that the object passed to the function is an array. This will do a depth first search for the ID.

Once you find the object you need to get the descendant children. I would make this a separate function for simplicity:

const data = [  {  "id":"5b9ce8d51dbb85944baddfa5","name":"EARBANG","parent_id":0,"status":"Inactive","children":[  {  "id":"5b9ce8d5d978f75e4b1584ba","name":"DIGINETIC","parent_id":"5b9ce8d51dbb85944baddfa5","status":"Active","children":[  {  "id":"5b9ce8d5cb79d63c8b38018c","name":"PREMIANT","parent_id":"5b9ce8d5d978f75e4b1584ba","status":"Active",}]}]},{  "id":"5b9ce8d51650fac75fa359c8","name":"GEEKOLOGY","parent_id":0,"status":"Active",},{  "id":"5b9ce8d59f52e801a2e40a97","name":"TOYLETRY","parent_id":0,"status":"Inactive",},{  "id":"5b9ce8d5d136fcfed2f3e0dd","name":"PAPRIKUT","parent_id":0,"status":"Inactive",},{  "id":"5b9ce8d53afb7a61e188c48e","name":"EYERIS","parent_id":0,"status":"Inactive",}];

// create an array of child ids
function getChildren(obj) {
  return (!Array.isArray(obj)) 
  ? []
  : obj.reduce((arr, curr) => arr.concat(curr.id, ...getChildren(curr.children)), [])
}

// find a particular id
function search(arr, key){
  if (Array.isArray(arr)) { 
    for (obj of arr){
      return (obj.id === key) 
      ? {id: obj.id, childs: getChildren(obj.children)}   // call getChildren once you've found the object
      : search(obj.children, key)
    }
  }
}

console.log(search(data, '5b9ce8d51dbb85944baddfa5'));

// find deeper nesting:
console.log(search(data, '5b9ce8d5d978f75e4b1584ba'));

It will return undefined if the ID is not found.

Mohammed Ashfaq · Accepted Answer · 2018-09-22 05:55:54Z

let input = [
  {
    id: '5b9ce8d51dbb85944baddfa5',
    name: 'EARBANG',
    parent_id: 0,
    status: 'Inactive',
    children: [
      {
        id: '5b9ce8d5d978f75e4b1584ba',
        name: 'DIGINETIC',
        parent_id: '5b9ce8d51dbb85944baddfa5',
        status: 'Active',
        children: [
          {
            id: '5b9ce8d5cb79d63c8b38018c',
            name: 'PREMIANT',
            parent_id: '5b9ce8d5d978f75e4b1584ba',
            status: 'Active'
          }
        ]
      }
    ]
  },
  {
    id: '5b9ce8d51650fac75fa359c8',
    name: 'GEEKOLOGY',
    parent_id: 0,
    status: 'Active'
  },
  {
    id: '5b9ce8d59f52e801a2e40a97',
    name: 'TOYLETRY',
    parent_id: 0,
    status: 'Inactive'
  },
  {
    id: '5b9ce8d5d136fcfed2f3e0dd',
    name: 'PAPRIKUT',
    parent_id: 0,
    status: 'Inactive'
  },
  {
    id: '5b9ce8d53afb7a61e188c48e',
    name: 'EYERIS',
    parent_id: 0,
    status: 'Inactive'
  }
];

function getNestedChildrenId(fileteredObject, children) {
  return fileteredObject.map(item => {
    children.push(item.id);
    if (item.children && item.children.length) {
      getNestedChildrenId(item.children, children);
    }
  });
}

function getParentAndChildrenId(parentId, data) {
  let result = { id: parentId, children: [] };
  let fileteredParent = data.find(({ id }) => id === parentId);
  if (fileteredParent.children) getNestedChildrenId(fileteredParent.children, result.children);
  return result;
}

console.log(getParentAndChildrenId('5b9ce8d51dbb85944baddfa5', input));

console.log(getParentAndChildrenId('5b9ce8d5d136fcfed2f3e0dd', input));

Ignacio · Accepted Answer · 2018-09-22 06:22:59Z

Here's a basic recursive way,

var data = [{
  "id": "5b9ce8d51dbb85944baddfa5",
  "name": "EARBANG",
  "parent_id": 0,
  "status": "Inactive",
  "children": [{
    "id": "5b9ce8d5d978f75e4b1584ba",
    "name": "DIGINETIC",
    "parent_id": "5b9ce8d51dbb85944baddfa5",
    "status": "Active",
    "children": [{
      "id": "5b9ce8d5cb79d63c8b38018c",
      "name": "PREMIANT",
      "parent_id": "5b9ce8d5d978f75e4b1584ba",
      "status": "Active",
    }]
  }]
}, {
  "id": "5b9ce8d51650fac75fa359c8",
  "name": "GEEKOLOGY",
  "parent_id": 0,
  "status": "Active",
}, {
  "id": "5b9ce8d59f52e801a2e40a97",
  "name": "TOYLETRY",
  "parent_id": 0,
  "status": "Inactive",
}, {
  "id": "5b9ce8d5d136fcfed2f3e0dd",
  "name": "PAPRIKUT",
  "parent_id": 0,
  "status": "Inactive",
}, {
  "id": "5b9ce8d53afb7a61e188c48e",
  "name": "EYERIS",
  "parent_id": 0,
  "status": "Inactive",
}];


function findChildren(obj, output, targetId, found) {
  var _found;
  obj.forEach((child) => {
    if (found || child.id === targetId) {
      if (found) output.push(child.id);
      _found = true;
    }
    if (child.children && child.children.length) {
      findChildren(child.children, output, targetId, _found);
    }
  });
  return output;
}

var res = findChildren(data, [], "5b9ce8d51dbb85944baddfa5");

console.log('res:', res);

Rafael · Accepted Answer · 2018-09-22 06:23:16Z

Depth-First Descent

Here is a generic implementation that stops recursing once the predicate function returns true (hopefully we can find gold in our loot):

var loot = {
        box_a: 'seaweed',
        box_b: {
                box_c: [
                        { box_d: 'tuna', box_e: ['gold', 'trash'] }
                ]
        }
};

function descend_obj(item, pred_fn) {
        if (item instanceof Array) {
                return item.some(it => {
                        return descend_obj(it, pred_fn);
                });
        } else if (typeof item === "object") {
                return Object.keys(item).some(k => {
                        return descend_obj(item[k], pred_fn);
                });
        } else {
                return pred_fn(item);
        }
}

let hasGold = descend_obj(loot, function isGold(item) {
        return (item === 'gold')
});

let msg = (hasGold)
        ? 'yaaaay!'
        : 'awwweee';
console.log(msg);//yaaaay!

Prashant Pimpale · Accepted Answer · 2018-09-22 07:13:29Z

0

You can use this approach:

  var array = [your array];

  function filter(array, id) {
   result = {
    id: id,
    children: []
   };

   array.map(val => {
    if (val.id == id) {
     findChildren(val, result);
    }
   });

   return result;
  }

  function findChildren(obj) {
   if (obj.children && Array.isArray(obj.children)) {
    obj.children.map(val => {
     if (val.id) {
      result.children.push(val.id);
     }
     if (val.children) {
      findChildren(val);
     }
    });
   }
  }

  var search = filter(array, '5b9ce8d51dbb85944baddfa5');

I think the code is clear and does not need explanation.

edited Sep 22, 2018 at 7:13

Prashant Pimpale

10.7k10 gold badges52 silver badges88 bronze badges

answered Sep 22, 2018 at 6:18

clay

1,0465 silver badges13 bronze badges

Comments

marzelin · Accepted Answer · 2018-09-22 07:52:22Z

I tend not to use recursion because recursion is harder to reason about that loops because:

To use recursion you have to know exactly what a function returns beforehand. Because you will call it before it is complete (in its own body).
With recursion, you have to keep in mind multiple copies of the same function because that's how recursion works - the function calls itself before it ends. It's hard not to get lost in a pile of exactly same objects. With loops is easier because one iteration ends before another starts.

As far as synchronous code is concerned, recursion can always be replaced with a loop.

Here's non recursive solution:

function findDescendants(data, key) {
  let ancestor;
  const ancestorStack = [data];      
  while (ancestorStack.length) { // 1- Find an object having id
    const current = ancestorStack.pop();
    for (const item of current) {
      if (item.id === key) {
        ancestor = item;
        break;
      }
      const { children } = current;
      if (children && children.length) {
        ancestorStack.push(children);
      }
    }
  }
  const descendantIds = [];      
  const childrenStack = [ancestor.children];
  while (childrenStack.length) { // 2- get id of all its descendants
    const current = childrenStack.pop();
    for (const item of current) {
      descendantIds.push(item.id);
      const { children } = item;
      if (children && children.length) {
        childrenStack.push(children);
      }
    }
  }
  return {
    id: ancestor.id,
    childs: descendantIds
  }
}

live demo: https://repl.it/@marzelin/findDescendants

Since this function performs two independent tasks, it would be good to outsource and generalize the tasks:

function findDeep(predicate, deepProps, data)
function gatherDeep(prop, deepProps, data)

Then findDecendants could be simplified to:

function findDescendants(data, key) {
  const ancestor = findDeep(o => o.id === key, ["children"], data);
  const descendantIds = gatherDeep("id", ["children"], ancestor.children);
  return {
    id: ancestor.id,
    childs: descendantIds
  }
}

Do not get me wrong but loops can also be used with recursion. Recursion is much more mindfull solution in these cases.

Berker Yüceer · Accepted Answer · 2020-01-21 08:14:55Z

I made myself a function for this which might be of use for you as well.

It helps a lot when you dont know what kind of object you are dealing with...

Example:

var values = [
      {  
        "id":"5b9ce8d51dbb85944baddfa5",
        "name":"EARBANG",
        "parent_id":0,
        "status":"Inactive",
        "children":[  
           {  
              "id":"5b9ce8d5d978f75e4b1584ba",
              "name":"DIGINETIC",
              "parent_id":"5b9ce8d51dbb85944baddfa5",
              "status":"Active",
              "children":[  
                 {  
                    "id":"5b9ce8d5cb79d63c8b38018c",
                    "name":"PREMIANT",
                    "parent_id":"5b9ce8d5d978f75e4b1584ba",
                    "status":"Active",
                 }
              ]
           }
        ]
     },
     {  
        "id":"5b9ce8d51650fac75fa359c8",
        "name":"GEEKOLOGY",
        "parent_id":0,
        "status":"Active",
     },
     {  
        "id":"5b9ce8d59f52e801a2e40a97",
        "name":"TOYLETRY",
        "parent_id":0,
        "status":"Inactive",
     },
     {  
        "id":"5b9ce8d5d136fcfed2f3e0dd",
        "name":"PAPRIKUT",
        "parent_id":0,
        "status":"Inactive",
     },
     {  
        "id":"5b9ce8d53afb7a61e188c48e",
        "name":"EYERIS",
        "parent_id":0,
        "status":"Inactive",
     }
  ]
  //---------------------------------------------------------
  // Strip Down to String Function
  //----------------------------------------------------------
  var depth = 0;
  var stripdown = function(object, find, eol) {
      depth = depth + 1;
      var str = "";
      var s = new function() {
          return {
              // Unique ID generator
              id: new Date().getFullYear() + 
                  new Date().getMonth() + 
                  new Date().getDate() + 
                  new Date().getHours() + 
                  new Date().getMinutes() + 
                  new Date().getSeconds() + 
                  new Date().getMilliseconds(),
              // Spaces for depth
              space: '    ',
              // Index
              index: 0
          }
      };
      while(s.index <= Object.keys(object).length){
          // Every Last Line Has An Undefined Object So Clear Them
          if (Object.keys(object)[s.index] != undefined) {
              // If More Than 1 In The Line Add ',' + eol
              if (s.index > 0) {
                str = str + ',' + eol;
              }
              // Add Spaces For Each Depth Level
              for(var i=0;i < depth;i++) { str = str + s.space; }
              // Add Keys
              str = str + Object.keys(object)[s.index] + ' : ';
              // Add Values
              if (typeof Object.values(object)[s.index] === 'object'){
                  str = str + '{' + eol; // Starting Tag
                  // Add Inner Object Values
                  str = str + stripdown(Object.values(object)[s.index], find, eol);
                  // Add Closing Space
                  for(var i=depth;i > 0;i--) { str = str + s.space; }
                  str = str + '}'; // Closing Tag
                  // Find Object
                  if(str.indexOf(find)>-1){
                    // Lower The Depth 
                    depth = depth - 1;
                    return str + eol;
                  }
              } else {
                  // No Sub Object
                  str = str + Object.values(object)[s.index];
              }
          }
          // Next line
          s.index = s.index + 1;
      }
      // Lower The Depth 
      depth = depth - 1;
      // Return
      return str + eol;
  }
  //---------------------------------------------------------
  console.log(stripdown(values, "PREMIANT", "\n"));

Usage:

stripdown( [object Object], SearchFor, "\n" );

Returns Object Tree as String;

0 : {
    id : 5b9ce8d51dbb85944baddfa5,
    name : EARBANG,
    parent_id : 0,
    status : Inactive,
    children : {
        0 : {
            id : 5b9ce8d5d978f75e4b1584ba,
            name : DIGINETIC,
            parent_id : 5b9ce8d51dbb85944baddfa5,
            status : Active,
            children : {
                0 : {
                    id : 5b9ce8d5cb79d63c8b38018c,
                    name : PREMIANT,
                    parent_id : 5b9ce8d5d978f75e4b1584ba,
                    status : Active
                }
            }
        }
    }
}

Collectives™ on Stack Overflow

Finding value in deep nested array of object, recursively, javascript

10 Answers 10

Comments

Comments

2 Comments

Comments

Comments

Comments

Depth-First Descent

Comments

Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

10 Answers 10

Comments

Comments

2 Comments

Comments

Comments

Comments

Depth-First Descent

Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related