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

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

• javascript

10 Answers 10

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

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

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

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.

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

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

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!

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.

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

1. To use recursion you have to know exactly what a function returns beforehand. Because you will call it before it is plete (in its own body).
2. 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
  }
}

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
                }
            }
        }
    }
}