I am new to data structures in JavaScript and am trying to learn Binary Search Trees. I was following along with a blog post and was able to get a working solution to the problem of finding the max depth in a BST, but it’s unclear to me how the recursion is working and how the +1 gets added on each time at each level of depth. What is a good way to think about this? Is it basically that each time the nodes value is not null, 1 gets added to what will eventually be returned up the call stack (i.e. at each level as it backtracks up to the root)?

function maxDepth(node) { // console.log(node.left); if (node) { return Math.max(maxDepth(node.left), maxDepth(node.right)) + 1; } else { return 0; } }

## Advertisement

## Answer

The code for `maxDepth(node)`

reads like this:

If

`node`

is not`null`

:- Run this same algorithm
`maxDepth`

on`node`

‘s left child. Let this answer be`x`

. - Run this same algorithm
`maxDepth`

on`node`

‘s right child. Let this answer be`y`

. - Calculate
`Math.max(x, y) + 1`

, and return this value as the answer for this function call.

- Run this same algorithm
Otherwise

`node`

is`null`

, then return`0`

.

This means when we try to compute `maxDepth(node)`

on a non-null node, we first compute `maxDepth()`

on both of `node`

‘s children, and let those two subcomputations finish. Then we take the maximum of these values, add 1, and return the result.

**Example:**

a / b f / c e g / d

Call stack:

a => max(b,f) b => max(c,e) c => max(d,null) d => max(null,null) d <= (0,0)+1 = 1 c <= (1,0)+1 = 2 e => max(null,null) e <= (0,0)+1 = 1 b <= (2,1)+1 = 3 f => (null,g) g => (null,null) g <= (0,0)+1 = 1 f <= (0,1)+1 = 2 a <= (3,2)+1 = 4