Why does calling the function MaxDepth here return the depth?

Question

class Node:
 
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Compute the "maxDepth" of a tree -- the number of nodes
# along the longest path from the root node down to the
# farthest leaf node
def maxDepth(node):
    if node is None:
        return 0 ;
 
    else :
 
        # Compute the depth of each subtree
        lDepth = maxDepth(node.left)   #HERE <--------------------
        rDepth = maxDepth(node.right)
 
        # Use the larger one
        if (lDepth > rDepth):
            return lDepth+1
        else:
            return rDepth+1
 
 
# Driver program to test above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
 
 
print ("Height of tree is %d" %(maxDepth(root)))

all this is doing is recursively going into maxDepth until there is no more node.left or node.right, how does this return the depth??

I have commented #HERE <--- to specify where I am confused. How does this code know what value to assign lDepth and rDepth??

Your code is missing the Class definition. - "class Node: ....". And it missed the recursive point. — Daniel Hao, Jun 05 '21 at 08:26
Does this answer your question? [Understanding recursion](https://stackoverflow.com/questions/717725/understanding-recursion) — tevemadar, Jun 05 '21 at 08:36

UziGoozie · Answer 1 · 2021-06-05T13:45:06.160

You can think of the function like this:

Every tree can be recursively thought of as a having two subtrees on its left and right. Therefore each tree's maximum depth is defined recursively as the maximum of the left and rights subtrees' depths plus one.

One can choose two kinds of equivalent bases cases for this recursion:

None nodes have depth 0
Nodes with no children (leafs) have depth 1.

In this case, you have chosen the first base case.

As an example, look at the graph below:

    A    <--- maxDepth(A) = max(maxDepth(B), maxDepth(C)) + 1
   / \
  B   C  <--- maxDepth(C) = 1, maxDepth(B) = max(maxDepth(D), maxDepth(E)) + 1
 / \
D   E   <---- maxDepth(D) = 1, maxDepth(E) = maxDepth(F) + 1
   /
  F     <---- maxDepth(F) = 1

Lavande · Accepted Answer · 2021-06-05T10:50:23.883

Below is a supplement to the previous answers. I've added some printouts into your original code in order to show how the recursion works step by step.

class Node:

    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


# Compute the "maxDepth" of a tree -- the number of nodes
# along the longest path from the root node down to the
# farthest leaf node
def maxDepth(node):
    if node:
        print(f"Current node: {node.data}")
    if node is None:
        print("Current node: None")
        return 0

    else:

        # Compute the depth of each subtree
        lDepth = maxDepth(node.left)  # HERE <--------------------
        print("lDepth traversal finished")
        rDepth = maxDepth(node.right)
        print("rDepth traversal finished")

        # Use the larger one
        if (lDepth > rDepth):
            print(f"lDepth: {lDepth} | rDepth: {rDepth}, return lDepth+1")
            return lDepth + 1
        else:
            print(f"lDepth: {lDepth} | rDepth: {rDepth}, return rDepth+1")
            return rDepth + 1


# Driver program to test above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Height of tree is %d" % (maxDepth(root)))

Current node: 1                           <--- caller: last line
Current node: 2                           <--- caller: lDepth = maxDepth(node.left) on tree lvl1 (node(1))
Current node: 4                           <--- caller: lDepth = maxDepth(node.left) on tree lvl2 (node(2))
Current node: None                        <--- caller: lDepth = maxDepth(node.left) on tree lvl3 (node(4))
lDepth traversal finished                 <--- back to tree lvl3 (node(4))
Current node: None                        <--- caller: rDepth = maxDepth(node.right) on tree lvl3 (node(4))
rDepth traversal finished                 <--- back to tree lvl3 (node(4))
lDepth: 0 | rDepth: 0, return rDepth+1
lDepth traversal finished                 <--- back to tree lvl2 (node(2))
Current node: 5                           <--- caller: rDepth = maxDepth(node.right) on tree lvl2 (node(2))
Current node: None                        <--- caller: lDepth = maxDepth(node.left) on tree lvl3 (node(5))
lDepth traversal finished                 <--- back to tree lvl3 (node(5))
Current node: None                        <--- caller: rDepth = maxDepth(node.right) on tree lvl3 (node(5))
rDepth traversal finished                 <--- back to tree lvl3 (node(5))
lDepth: 0 | rDepth: 0, return rDepth+1
rDepth traversal finished                 <--- back to tree lvl2 (node(2))
lDepth: 1 | rDepth: 1, return rDepth+1
lDepth traversal finished                 <--- back to tree lvl1 (node(1))
Current node: 3                           <--- caller: rDepth = maxDepth(node.right) on tree lvl1 (node(1))
Current node: None                        <--- caller: lDepth = maxDepth(node.left) on tree lvl2 (node(3))
lDepth traversal finished                 <--- back to tree lvl2 (node(3))
Current node: None                        <--- caller: rDepth = maxDepth(node.right) on tree lvl2 (node(3))
rDepth traversal finished                 <--- back to tree lvl2 (node(3))
lDepth: 0 | rDepth: 0, return rDepth+1
rDepth traversal finished                 <--- back to tree lvl1 (node(1))
lDepth: 2 | rDepth: 1, return lDepth+1    <--- finish recursion
Height of tree is 3

Why does calling the function MaxDepth here return the depth?

2 Answers2