I need to filter objects recursively in a deeply nested array of objects using javascript, maybe with the help of lodash. What is the cleanest way to do it, If I don't know how many nested object there will be in my array?

Let's say I have the following structure

[
  {
    label: "first",
    id: 1,
    children: []
  },
  {
    label: "second",
    id: 2,
    children: [
      {
        label: "third",
        id: 3,
        children: [
          {
            label: "fifth",
            id: 5,
            children: []
          },
          {
            label: "sixth",
            id: 6,
            children: [
              {
                label: "seventh",
                id: 7,
                children: []
              }
            ]
          }
        ]
      },
      {
        label: "fourth",
        id: 4,
        children: []
      }
    ]
  }
];

I want to find the one with id 6, and if it has children return true otherwise false.

Of course If I have a similar data structure but with different number of items it should work too.

I need to filter objects recursively in a deeply nested array of objects using javascript, maybe with the help of lodash. What is the cleanest way to do it, If I don't know how many nested object there will be in my array?

Let's say I have the following structure

[
  {
    label: "first",
    id: 1,
    children: []
  },
  {
    label: "second",
    id: 2,
    children: [
      {
        label: "third",
        id: 3,
        children: [
          {
            label: "fifth",
            id: 5,
            children: []
          },
          {
            label: "sixth",
            id: 6,
            children: [
              {
                label: "seventh",
                id: 7,
                children: []
              }
            ]
          }
        ]
      },
      {
        label: "fourth",
        id: 4,
        children: []
      }
    ]
  }
];

I want to find the one with id 6, and if it has children return true otherwise false.

Of course If I have a similar data structure but with different number of items it should work too.

• javascript
• lodash

• You can write a function that can iterate over the top-level items, and then modify that function to accept an input array to iterate over, and then have that function call itself recursively for each item's children. – user229044 ♦ Commented Nov 19, 2018 at 20:12
• are any of the children refs to parents? that can cause an infinite loop when iterating. otherwise, it's a pretty straight-forward for/in, recursively calling if the typeof all[specific] =='object. – dandavis Commented Nov 19, 2018 at 20:15

9 Answers 9

Since you only want a true of false answer you can use some() on the recursion, effectively doing a depth-first search, and make it pretty succinct:

let arr = [{label: "first",id: 1,children: []},{label: "second",id: 2,children: [{label: "third",id: 3,children: [{label: "fifth",id: 5,children: []},{label: "sixth",id: 6,children: [{label: "seventh",id: 7,children: []}]}]},{label: "fourth",id: 4,children: []}]}];

function findNested(arr, id) {
    let found = arr.find(node => node.id === id)
    return found 
      ? found.children.length > 0 
      : arr.some((c) => findNested(c.children, id))

} 

console.log(findNested(arr, 6))  // True: found with children
console.log(findNested(arr, 7))  // False: found no children
console.log(findNested(arr, 97)) // False: not found

Perhaps a recursive solution along the lines of this might work for you? Here, the node with supplied id is recursively searched for through the 'children' of the supplied input data. If a child node with matching id is found, a boolean result is returned based on the existence of data in that nodes children array:

function nodeWithIdHasChildren(children, id) {
  
  for(const child of children) {

    // If this child node matches supplied id, then check to see if
    // it has data in it's children array and return true/false accordinly
    if(child.id === id) {
    
      if(Array.isArray(child.children) && child.children.length > 0) {
        return true
      }
      else {
        return false
      }
    }
    else {
    
      const result = nodeWithIdHasChildren(child.children, id);

      // If result returned from this recursion branch is not undefined
      // then assume it's true or false from a node matching the supplied
      // id. Pass the return result up the call stack
      if(result !== undefined) {
        return result
      }
    }
  }  
}

const data = [
  {
    label: "first",
    id: 1,
    children: []
  },
  {
    label: "second",
    id: 2,
    children: [
      {
        label: "third",
        id: 3,
        children: [
          {
            label: "fifth",
            id: 5,
            children: []
          },
          {
            label: "sixth",
            id: 6,
            children: [
              {
                label: "seventh",
                id: 7,
                children: []
              }
            ]
          }
        ]
      },
      {
        label: "fourth",
        id: 4,
        children: []
      }
    ]
  }
];



console.log('node 6 has children:', nodeWithIdHasChildren( data, 6 ) )

console.log('node 7 has children:', nodeWithIdHasChildren( data, 7 ) )

console.log('node 100 has children:', nodeWithIdHasChildren( data, 7 ), '(because node 100 does not exist)' )

Here is another solution using recursion and doing it via only one Array.find:

const data = [ { label: "first", id: 1, children: [] }, { label: "second", id: 2, children: [ { label: "third", id: 3, children: [ { label: "fifth", id: 5, children: [] }, { label: "sixth", id: 6, children: [ { label: "seventh", id: 7, children: [] } ] } ] }, { label: "fourth", id: 4, children: [] } ] } ];

const search = (data, id) => {
  var f, s = (d, id) => d.find(x => x.id == id ? f = x : s(x.children, id))	
  s(data, id)
  return f ? f.children.length > 0 : false
}

console.log(search(data, 6))  // True: found with children
console.log(search(data, 7))  // False: found but has no children
console.log(search(data, 15)) // False: not found at all

The idea is to have a recursive function which when finds the id remembers the object.

Once we have the found (or we know we do not have an entry found) just return the children array length or return false.

If you want to actually return the found object instead of the boolean for children.length:

const data = [ { label: "first", id: 1, children: [] }, { label: "second", id: 2, children: [ { label: "third", id: 3, children: [ { label: "fifth", id: 5, children: [] }, { label: "sixth", id: 6, children: [ { label: "seventh", id: 7, children: [] } ] } ] }, { label: "fourth", id: 4, children: [] } ] } ];

const search = (data, id) => {
  var f, s = (d, id) => d.find(x => x.id == id ? f = x : s(x.children, id))	
  s(data, id)
  return f
}

console.log(search(data, 6))  // returns only the object with id:6
console.log(search(data, 7))  // returns only the object with id: 7
console.log(search(data, 71)) // returns undefined since nothing was found

The JSON.parse reviver parameter or the JSON.stringify replacer parameter can be used to check all values, and generate flat id lookup object with references to the nodes :

var lookup = {}, json = '[{"label":"first","id":1,"children":[]},{"label":"second","id":2,"children":[{"label":"third","id":3,"children":[{"label":"fifth","id":5,"children":[]},{"label":"sixth","id":6,"children":[{"label":"seventh","id":7,"children":[]}]}]},{"label":"fourth","id":4,"children":[]}]}]'

var result = JSON.parse(json, (key, val) => val.id ? lookup[val.id] = val : val);

console.log( 'id: 2, children count:', lookup[2].children.length )
console.log( 'id: 6, children count:', lookup[6].children.length )
console.log( lookup )

I suggest to use deepdash extension for lodash:

var id6HasChildren = _.filterDeep(obj,
  function(value, key, parent) {
    if (key == 'children' && parent.id == 6 && value.length) return true;
  },
  { leavesOnly: false }
).length>0;

Here is a docs for filterDeep.

And this a full test for your case.

You can use "recursion" like below to check if id has children or not

let arr = [{label: "first",id: 1,children: []},{label: "second",id: 2,children: [{label: "third",id: 3,children: [{label: "fifth",id: 5,children: []},{label: "sixth",id: 6,children: [{label: "seventh",id: 7,children: []}]}]},{label: "fourth",id: 4,children: []}]}];

function hasChildren(arr, id) {
  let res = false
  for (let d of arr) {
    if(d.id == id) return d.children.length > 0
    res = res || hasChildren(d.children, id)
    if(res) return true
  }
  return res
}

console.log('id 4 has children? ', hasChildren(arr, 4))
console.log('id 6 has children? ', hasChildren(arr, 6))

You can do it using three simple javascript functions:

// Function to Flatten results
var flattenAll = function(data) {
  var result = [];
  var flatten = function(arr) {
    _.forEach(arr, function(a) {
      result.push(a);
      flatten(a.children);
    });
  };
  flatten(data);
  return result;  
};

// Function to search on flattened array
var search = function(flattened, id) {
  var found = _.find(flattened, function(d) { 
              return d.id == id;
            });
  return found;
};

// Function to check if element is found and have children
var hasChildren = function(element) {
  return element && element.children && element.children.length > 0;
}

// Usage, search for id = 6
hasChildren(search(flattenAll(your_data_object), 6))

Plunker

You can use a generator function to iterate the nodes recursively and simplify your logic for checking existence by using Array.prototype.some():

const data = [{label:'first',id:1,children:[]},{label:'second',id:2,children:[{label:'third',id:3,children:[{label:'fifth',id:5,children:[]},{label:'sixth',id:6,children:[{label:'seventh',id:7,children:[]}]}]},{label:'fourth',id:4,children:[]}]}];

function * nodes (array) {
  for (const node of array) {
    yield node;
    yield * nodes(node.children);
  }
}

const array = Array.from(nodes(data));

console.log(array.some(node => node.id === 6 && node.children.length > 0));
console.log(array.some(node => node.id === 7 && node.children.length > 0));

We now use object-scan for data processing needs like this. It's very powerful once you wrap your head around it. This is how you could solve your questions

// const objectScan = require('object-scan');

const hasChildren = (e) => e instanceof Object && Array.isArray(e.children) && e.children.length !== 0;
const find = (id, input) => {
  const match = objectScan(['**'], {
    abort: true,
    rtn: 'value',
    filterFn: ({ value }) => value.id === id
  })(input);
  return hasChildren(match);
};

const data = [{ label: 'first', id: 1, children: [] }, { label: 'second', id: 2, children: [{ label: 'third', id: 3, children: [{ label: 'fifth', id: 5, children: [] }, { label: 'sixth', id: 6, children: [{ label: 'seventh', id: 7, children: [] }] }] }, { label: 'fourth', id: 4, children: [] }] }];

console.log(find(6, data));
// => true
console.log(find(2, data));
// => true
console.log(find(7, data));
// => false
console.log(find(999, data));
// => false

.as-console-wrapper {max-height: 100% !important; top: 0}

<script src="https://bundle.run/[email protected]"></script>

Disclaimer: I'm the author of object-scan