How Do I Write This Recursive Function To Find The Max Depth Of My Object?

July 27, 2023 Post a Comment

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: 'i

Solution 1:

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

functiongetDepth(object) {
    return1 + 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 basedconsole.log(depth);

Solution 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.

constdepth = ({ 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

constdepth = ({ 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

constdepth = ({ 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

constisEmpty = (xs = []) =>
  xs.length === 0constfirst = (xs = []) =>
  xs [0]

constrest = (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 number1 + 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

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

All that's left is to define max

constmax = (x = 0, y = 0) =>
  x > y
    ? x
    : y

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

constmax = (x = 0, y = 0) =>
  x > y
    ? x
    : y

constisEmpty = (xs = []) =>
  xs.length === 0constfirst = (xs = []) =>
  xs [0]

constrest = (xs = []) =>
  xs.slice (1)

constdepth = ({ children = [] }) =>
  children.length === 0
    ? 0// base
    : 1 + magicWand (children) // inductiveconstmagicWand = (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

constmagicWand = (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.

constdepth = ({ 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

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

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

constisEmpty = (xs = []) =>
  xs.length === 0constfirst = (xs = []) =>
  xs [0]
  
constrest = (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

constmagicWand2 = (f, g) =>
  (acc, x) => g (acc, f (x))

constdepth = ({ 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

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

constmap = (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.

constfilter = (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))

m, the mapping function – this gives you a chance to transform the incoming element before ...
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

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

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

constsquare = x =>
  x * x

constgt = 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...

constdepth = ({ 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 ]. Thenmap 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!

Solution 3:

Here's a proposal:

functiondepth(o){
  var values;
  if (Array.isArray(o)) values = o;
  elseif (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'
      }]
    }]
  }]
};

functiondepth(o){
  var values;
  if (Array.isArray(o)) values = o;
  elseif (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).

Solution 4:

I have changed your code a bit to work as you want it to:

functiongetDepth(node, depth = 0) {
    if (!!node.children && node.children.length > 0) {
        var childDepths = [];
        depth++;

        for (var i = 0; i < node.children.length; i++) {
            childDepths.push(getDepth(node.children[i]));
        }
        return depth + Math.max(...childDepths);
    }

    return depth;
}

var depth = getDepth(root);

console.log('currentMaxDepth', depth);
console.log('root', root);

The trick is to measure depths of siblings on the same level and than pick the deepest of them. Here's also a jsfiddle: https://jsfiddle.net/2xk7zn00/

Solution 5:

In the function

functiongetMaxDepth(root) {
    var currentMaxDepth = 0;

    returngetDepth(currentMaxDepth, root);
}

You call getDepth with root, but root is never changed. So it is always the same. You should call for instance,

return getDepth(currentMaxDepth, root.children[0]);

JavaScript Controls