Find deep nested array depth

Question

I have a nested array. Like below: I want to find the depth of this nested array, which means the child element has most deep nested children.

let arr = [
   {
     name: 'tiger',
     children: [{
       name: 'sinba',
       children: [{
         name: 'cute',
         children: []
        }]
      }]
    },
    {
      name: 'lion',
      children: []
    }
]

In this case, the depth is 3, the tiger has 3 level. So the depth is 3

How could i achieve this? I try to use recursive, but don't know how to find the element which has most nested children.

Thanks in advance.

Krzysztof Krzeszewski · Accepted Answer · 2020-08-21 09:04:45Z

3

Assuming that there are no circular references, you could try something like this

let arr = [{
    name: 'tiger',
    children: [{
      name: 'sinba',
      children: [{
        name: 'cute',
        children: []
      }]
    }]
  },
  {
    name: 'lion',
    children: []
  }
]

function count(children) {
  return children.reduce((depth, child) => {
    return Math.max(depth, 1 + count(child.children)); // increment depth of children by 1, and compare it with accumulated depth of other children within the same element
  }, 0); //default value 0 that's returned if there are no children
}

console.log(count(arr))

Our function would not work if there were some circular references, so there might be a need to adjust it accordingly. Detecting circular references is a whole ordeal. If nothing is done about it, the function will throw a Maximum call stack size exceeded error.

In order to handle it without any additional functionality implementation you could use already existing native JSON.stringify to do so. The stringify option will throw an exception only if you try to serialize BigInt values which we can handle ourselves or when objects are cyclic, which is excatly what we wanted.

let arr = [{
  name: 'tiger',
  children: []
}]

function testCircular(arr){
  try {
    BigInt.prototype.toJSON = function() { return this.toString() } // Instead of throwing, JSON.stringify of BigInt now produces a string
    JSON.stringify(arr);
    return false;
  }
  catch (e) {
    // will only enter here in case of circular references
    return true;
  }
}

function count(children) {
  if (testCircular(children)) return Infinity;
  return children.reduce((depth, child) => {
    return Math.max(depth, 1 + count(child.children)); // increment depth of children by 1, and compare it with accumulated depth of other children within the same element
  }, 0); //default value 0 that's returned if there are no children
}

console.log(count(arr)) // normally counting
arr[0].children = arr; // creates circular reference
console.log(count(arr)) // counting for circular

edited Aug 21, 2020 at 9:04

answered Aug 21, 2020 at 8:19

Krzysztof Krzeszewski

6,8382 gold badges23 silver badges33 bronze badges

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

5 Comments

Kunal Mukherjee Over a year ago

why the Math.max and comparing ?

Krzysztof Krzeszewski Over a year ago

@KunalMukherjee reduce function iterated over all children elements, I need to compare results of counting children of children with each other to know which one has the most and only keep information on it. Granted i only compare at most 2 elements at a time i could probably use a simple if else statement, but max works just as well

Kunal Mukherjee Over a year ago

Nice solution !

Mulan Over a year ago

note the BigInt extension will not JSON.parse large numbers back to BigInt. Eg JSON.parse("999999999999999999999999999999999999999999") returns 1e+42

Krzysztof Krzeszewski Over a year ago

here it's only used to remove the error throwing not to actually parse the data

Collectives™ on Stack Overflow

Find deep nested array depth

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related