Explain how recursion works in an algorithm to determine depth of binary tree?

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;
}
}
```

The code for `maxDepth(node)` reads like this:

1. If `node` is not `null`:

1. Run this same algorithm `maxDepth` on `node`‘s left child. Let this answer be `x`.
2. Run this same algorithm `maxDepth` on `node`‘s right child. Let this answer be `y`.
3. Calculate `Math.max(x, y) + 1`, and return this value as the answer for this function call.
2. 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
```
User contributions licensed under: CC BY-SA
2 People found this is helpful
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}