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

Let me rewrite the code in a little simpler way for the sake of an easy and better explanation.

function maxDepth(node) {
  if (node == null)
      return 0;
  else {
      l = maxDepth(node.left)
      r = maxDepth(node.right)
      return Math.max(left, right) + 1;
  }
}

Now, let's explain the above recursion with the following tree:

      A
     / \
    B   C
   /    
  D      
            

The function maxDepth(node) get called with the root (A), therefore, we will explain our recursion stack pictorially starting from node A:

A
| l = ?
|-------> B
|         | l = ?
|         |-------> D
|         |         | l = ?
|         |         |-------> null (return 0)

A
| l = ?
|-------> B
|         | l = ?
|         |-------> D
|         |         | l = 0 <---------|
|         |         |-------> null (return 0)

A
| l = ?
|-------> B
|         | l = ?
|         |-------> D
|         |         | l = 0 
|         |         |
|         |         | r = ?
|         |         |-------> null (return 0)

A
| l = ?
|-------> B
|         | l = ?
|         |-------> D
|         |         | l = 0 
|         |         |
|         |         | r = 0 <---------|
|         |         |-------> null (return 0)

A
| l = ?
|-------> B
|         | l = ? <--------------------------|
|         |-------> D                        |
|         |         | l = 0                  |
|         |         |          max(0,0)+1 => 1
|         |         | r = 0 


A
| l = ?
|-------> B
|         | l = 1 <--------------------------|
|         |-------> D                        |
|         |         | l = 0                  |
|         |         |          max(0,0)+1 => 1
|         |         | r = 0 


A
| l = ?
|-------> B
|         | l = 1 
|         |
|         | r = ? 
|         | -------> null (return 0)

A
| l = ?
|-------> B
|         | l = 1 
|         |
|         | r = 0 <---------| 
|         | -------> null (return 0)


A
| l = ? <--------------------------|
|-------> B                        |
|         | l = 1                  | 
|         |          max(1,0)+1 => 2
|         | r = 0

A
| l = 2 <--------------------------|
|-------> B                        |
|         | l = 1                  | 
|         |          max(1,0)+1 => 2
|         | r = 0

A
| l = 2 
|
| r = ?        
| -------> C 
|          | l = ? <---------| 
|          |-------> null (return 0)

A
| l = 2 
|
| r = ?        
| -------> C 
|          | l = 0 
|          |
|          | r = ? <---------| 
|          |-------> null (return 0)

A
| l = 2 
|
| r = ? <---------------------------|        
| -------> C                        | 
|          | l = 0                  | 
|          |          max(0,0)+1 => 1
|          | r = 0 

A
| l = 2 
|
| r = 1 <---------------------------|        
| -------> C                        | 
|          | l = 0                  | 
|          |          max(0,0)+1 => 1
|          | r = 0 


A <----------------------|  
| l = 2                  |  
|          max(2,1)+1 => 3
| r = 1 

Finally, A returns 3.

3
^
|
A (3)<-------------------|  
| l = 2                  |  
|          max(2,1)+1 => 3
| r = 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