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

The top half of your question, with the maxDepth() function, is enough scope for us to answer. You can delete the second block of code. — Nayuki
– Nayuki, Commented Nov 29, 2015 at 0:26

Sam Segers · Accepted Answer · 2015-11-29 01:17:49Z

16

The code for maxDepth(node) reads like this:

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

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

edited Nov 29, 2015 at 1:17

Sam Segers

1,9512 gold badges22 silver badges30 bronze badges

answered Nov 29, 2015 at 0:30

Nayuki

18.8k6 gold badges61 silver badges84 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

mazhar islam · Accepted Answer · 2020-12-16 02:44:44Z

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:

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

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related