How do I write this recursive function to find the max depth of my object?

Question

I'm trying to write a function that will loop through my object and return the level depth of the object.

For example, if I ran the function on this object:

var test = {
  name: 'item 1',
  children: [{
    name: 'level 1 item',
    children: [{
      name: 'level 2 item'
    },
    {
      name: 'second level 2 item',
      children: [{
        name: 'level 3 item'
      }]
    }]
  }]
}

var depth = myFunction(test); // Would return 2 (0 index based) as the collection goes 3 levels deep

I've been trying to write a recursive function that determines the maximum depth but so far I can't get it right. This is what I have so far: https://jsfiddle.net/6cc6kdaw/2/

It seems the value returned is a count of every node hit, not unique levels. I understand where I'm going wrong (in the sense that I'm not filtering this out) but I'm at the point where I've been staring at the code for so long that nothing's making sense any more!

Anyone able to point out where I'm going wrong? Thanks

Answer 1

You could map the depth of every children and take the maximum value of it.

function getDepth(object) {
    return 1 + Math.max(0, ...(object.children || []).map(getDepth));
}

var test = { name: 'item 1', children: [{ name: 'level 1 item', children: [{ name: 'level 2 item' }, { name: 'second level 2 item', children: [{ name: 'level 3 item' }] }] }] },
    depth = getDepth(test) - 1; // zero based

console.log(depth);

Answer 2

beauty

The depth function is one of those functions that's expressed so beautifully with recursion – this answer is similar to Nina's but illustrates a different line of reasoning.

const depth = ({ children = [] }) =>
  children.length === 0
    ? 0                                      // base
    : 1 + Math.max (...children.map (depth)) // inductive

First we destructure the incoming node, assigning children = [] when the property isn't set. This allows us to attack the problem using the traditional base and inductive cases for arrays:

• base case: the array is empty
• inductive case: the array is not empty, therefore we have at least one element to handle

Nina's answer very cleverly avoids any if or ternary ?: altogether! She does this by sneaking the base case in as the first argument to Math.max! She's so smart <3

Here's a functioning example

const depth = ({ children = [] }) =>
  children.length === 0
    ? 0
    : 1 + Math.max (...children.map (depth))

const test = 
  { name: 'level 0 item'
  , children: 
      [ { name: 'level 1 item'
        , children:
            [ { name: 'level 2 item' }
            , { name: 'second level 2 item'
              , children:
                  [ { name: 'level 3 item' } ]
              }
            ]
        }
      , { name: 'second level 1 item'
        , children:
            [ { name: 'level 2 item' }
            , { name: 'second level 2 item'
              , children: 
                  [ { name: 'level 3 item'
                    , children:
                        [ { name: 'level 4 item' } ]
                    }
                  ]
              }
            ]
        }
      ]
  }

console.log (depth (test))
// 4

---

the beast

We used some high-level functions and language utilities above. If we are new to this concept, we cannot achieve higher-level thinking before first learning to think at the lower levels

• Math.max accepts any number of arguments. How does this work exactly?
• We use rest argument syntax ...children to convert an array of values as individual arguments in a function call. How does this conversion work exactly?
• We use map from the Array.prototype to transform our array of children nodes into an array of node depths. How does this work? Do we really need to make a new array?

To foster an appreciation for these built-in functions and features, we'll look at how to achieve such results on our own. We'll revisit depth but this time we'll replace all of that magic with our own hard work

const depth = ({ children = [] }) =>
  children.length === 0
    ? 0                        // base
    : 1 + magicWand (children) // inductive

Now we just need a magic wand... first, we start with some basic crafting materials

const isEmpty = (xs = []) =>
  xs.length === 0

const first = (xs = []) =>
  xs [0]

const rest = (xs = []) =>
  xs.slice (1)

I want to keep thinking about the base and inductive cases, and these primitive functions compliment that line of reasoning.

Let's first get an intuition for how magicWand will (must) work

// magicWand takes a list of nodes and must return a number
1 + magicWand (children)

So let's look at our two cases

• base case: the input list isEmpty, so return 0 – there are no children, so there is no depth to add
• inductive case: there list has at least one child – calculate the depth of the first item, wave the magic wand on the rest, and take the max of those two values

Our magic wand is complete

const magicWand = (list = []) =>
  isEmpty (list)
    // base
    ? 0
    // inductive
    : max ( depth (first (list))
          , magicWand (rest (list))
          )

All that's left is to define max

const max = (x = 0, y = 0) =>
  x > y
    ? x
    : y

Just to make sure everything is still working at this point...

const max = (x = 0, y = 0) =>
  x > y
    ? x
    : y

const isEmpty = (xs = []) =>
  xs.length === 0

const first = (xs = []) =>
  xs [0]

const rest = (xs = []) =>
  xs.slice (1)

const depth = ({ children = [] }) =>
  children.length === 0
    ? 0                        // base
    : 1 + magicWand (children) // inductive
    
const magicWand = (list = []) =>
  isEmpty (list)
    // base
    ? 0
    // inductive
    : max ( depth (first (list))
          , magicWand (rest (list))
          )

const test = 
  { name: 'level 0 item'
  , children: 
      [ { name: 'level 1 item'
        , children:
            [ { name: 'level 2 item' }
            , { name: 'second level 2 item'
              , children:
                  [ { name: 'level 3 item' } ]
              }
            ]
        }
      , { name: 'second level 1 item'
        , children:
            [ { name: 'level 2 item' }
            , { name: 'second level 2 item'
              , children: 
                  [ { name: 'level 3 item'
                    , children:
                        [ { name: 'level 4 item' } ]
                    }
                  ]
              }
            ]
        }
      ]
  }

console.log (depth (test)) // 4

So to achieve higher-level thinking, you must first visualize what will happen when your program is run

const someList =
  [ x, y, z ]

magicWand (someList)
// ???

It doesn't matter what x, y and z are. You just have to imagine the function call stack that magicWand will build with each of the independent pieces. We can see how this would expand as more items are added to the input list...

max ( depth (x)
    , max ( depth (y)
          , max ( depth (z)
                , 0
                )
          )
    )

When we see the computation that our functions build, we start to see similarities in their structure. When a pattern emerges, we can capture its essence in a reusable function

In the computation above, max and magicWand are hard-coded into our program. If I wanted to compute a different value with the tree, I'd need an entirely different magic wand.

This function is called a fold because it folds a user-supplied function f between each element in a traversable data structure. You'll see our signature base and inductive cases

const fold = (f, base, list) =>
  isEmpty (list)
    ? base
    : f ( fold ( f
               , base
               , rest (list)
               )
        , first (list)
        )

Now we can rewrite magicWand using our generic fold

const magicWand = (list = []) =>
  fold ( (acc, x) => max (acc, depth (x))
       , 0
       , list
       )

The magicWand abstraction is no longer necessary. fold can be used directly in our original function.

const depth = ({ children = [] }) =>
  children.length === 0
    ? 0
    : 1 + fold ( (acc, x) => max (acc, depth (x))
               , 0
               , children
               )

Of course it's much harder to read the original. Syntax sugars afford you all sorts of shortcuts in your code. The downside is beginners often feel there must always be some sort of sugary sweet "shorthand" solution to whatever their problem is – then they're stuck when it's just not there.

Functioning code example

const depth = ({ children = [] }) =>
  isEmpty (children)
    ? 0
    : 1 + fold ( (acc, x) => max (acc, depth (x))
               , 0
               , children
               )

const fold = (f, base, list) =>
  isEmpty (list)
    ? base
    : f ( fold ( f
               , base
               , rest (list)
               )
        , first (list)
        )
        
const max = (x = 0, y = 0) =>
  x > y
    ? x
    : y

const isEmpty = (xs = []) =>
  xs.length === 0
  
const first = (xs = []) =>
  xs [0]
  
const rest = (xs = []) =>
  xs.slice (1)

const test = 
  { name: 'level 0 item'
  , children: 
      [ { name: 'level 1 item'
        , children:
            [ { name: 'level 2 item' }
            , { name: 'second level 2 item'
              , children:
                  [ { name: 'level 3 item' } ]
              }
            ]
        }
      , { name: 'second level 1 item'
        , children:
            [ { name: 'level 2 item' }
            , { name: 'second level 2 item'
              , children: 
                  [ { name: 'level 3 item'
                    , children:
                        [ { name: 'level 4 item' } ]
                    }
                  ]
              }
            ]
        }
      ]
  }

console.log (depth (test))
// 4

beast mode

Lurking in the last implementation of depth we saw this lambda (anonymous function) expression.

(acc, x) => max (acc, depth (x))

We are about to bear witness to an incredible invention of our own making. This little lambda is so useful we'll actually give it a name, but before we can harness its true power, we must first make max and depth parameters – we've crafted a new magic wand

const magicWand2 = (f, g) =>
  (acc, x) => g (acc, f (x))

const depth = ({ children = [] }) =>
  isEmpty (children)
    ? 0
    : 1 + fold (magicWand2 (depth, max), 0, children)

// Tada!

At first glance you think this must be the most useless magic wand ever! You might suspect I'm one of those zombies that won't stop until everything is point-free. You inhale and suspend your reactions for a brief moment

const concat = (xs, ys) =>
  xs.concat (ys)

const map = (f, list) =>
  fold (magicWand2 (f, concat), [], list)

map (x => x * x, [ 1, 2, 3, 4 ])
// => [ 16, 9, 4, 1 ]

Admittedly, we think that's pretty cool. But we won't be dazzled by a 2-trick pony. You'd be wise to prevent just any old function from landing in your program or library, but you'd be a fool to overlook this one.

const filter = (f, list) =>
  fold ( magicWand2 (x => f (x) ? [ x ] : [], concat)
       , []
       , list
       )

filter (x => x > 2, [ 1, 2, 3, 4 ])
// [ 4, 3 ]

Ok, aside from the fact that map and filter are assembling the result in "reverse" order, this magic wand has some serious heat. We'll call it mapReduce because it gives us two parameters, each of them a function, and creates a new reducing function to plug into fold

const mapReduce => (m, r) =>
  (acc, x) => r (acc, m (x))

1. m, the mapping function – this gives you a chance to transform the incoming element before ...
2. r, the reducing function – this function combines the accumulator with the result of the mapped element

As for fold assembling the result in "reverse", it's not. This just happens to be a right-fold. Below, we can imagine f as some binary function (ie +) – see the computations in prefix notation f (x y), and infix notation x + y should help highlight the key difference

foldR (f, base, [ x, y, z ])
// = f (f (f (base, z), y), x)
// = ((base + z) + y) + x

foldL (f, base, [ x, y, z ])
// = f (f (f (base, x), y), z)
// = (((base + x) + y) + z

So let's define our left-fold, foldL now – I renamed fold to foldR and placed it here so we can see them side by side.

const foldL = (f, base, list) =>
  isEmpty (list)
    ? base
    : foldL ( f
            , f (base, first (list))
            , rest (list)
            )

const foldR = (f, base, list) =>
  isEmpty (list)
    ? base
    : f ( foldR ( f
               , base
               , rest (list)
               )
        , first (list)
        )

Many JavaScript developer don't know reduceRight exists on the Array.prototype. If you've only ever used commutative functions with reduce, you wouldn't be able to detect the difference.

Ok, so to fix our map and filter, we just have to replace our fold binding with foldL

const map = (f, list) =>
  foldL (mapReduce (f, concat), [], list)

const filter = (f, list) =>
  foldL (mapReduce (x => f (x) ? [ x ] : [], concat), [], list)

const square = x =>
  x * x

const gt = x => y =>
  y > x

map (square, filter (gt (2), [ 1, 2, 3, 4 ]))
// => [ 9, 16 ]

With our own map, we could rewrite depth a little closer to our original form...

const depth = ({ children = [] }) =>
  isEmpty (children)
    ? 0
    : 1 + foldL ( max
                , 0
                , map (depth, children)
                )

But I want us to stop there and think about why that's actually worse than depth that uses mapReduce directly...

Enough is enough

Let's just take a moment and think about what we did there with the map-filter example. filter steps through our entire input array, calling gt (2) for each number, producing an intermediate result of [ 3, 4 ]. Then map calls squarefor number in the intermediate result, producing a final value of [ 9, 16 ]. Data gets big and we don't want to see code like this:

myBigData.map(f).map(g).filter(h).map(i).map(j).reduce(k, base)

mapReduce is has the kind of power that will corrupt its beholder. You think I write this answerette willingly, but I'm just a prisoner of mapReduce! This structure is at the heart of something some communities call transducers – which happens to be a subject I've written about here on SO. We develop a fold of folds intuition – and like magic, exhausting multiple loops are collapsed into a single fold. If you're interested in the subject, I encourage you to read further!

Answer 3

Here's a proposal:

function depth(o){
  var values;
  if (Array.isArray(o)) values = o;
  else if (typeof o === "object") values = Object.keys(o).map(k=>o[k]);
  return values ? Math.max.apply(0, values.map(depth))+1 : 1;
}

var test = {
  name: 'item 1',
  children: [{
    name: 'level 1 item',
    children: [{
      name: 'level 2 item'
    },
    {
      name: 'second level 2 item',
      children: [{
        name: 'level 3 item'
      }]
    }]
  }]
};

function depth(o){
  var values;
  if (Array.isArray(o)) values = o;
  else if (typeof o === "object") values = Object.keys(o).map(k=>o[k]);
  return values ? Math.max.apply(0, values.map(v=>depth(v)))+1 : 1;
}

console.log(depth(test))

EDIT: this is a generic solution. I'm still unsure whether you wanted a very specific one (i.e. with a children field or a generic one).