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

Question

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

Answer 1

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