Question about Find the maximum depth of a tree

1
votes
maxDepth('1') = max(maxDepth('2'), maxDepth('3')) + 1
                               = 2 + 1
                                  /    \
                                /         \
                              /             \
                            /                 \
                          /                     \
               maxDepth('2') = 1                maxDepth('3') = 1
= max(maxDepth('4'), maxDepth('5')) + 1
= 1 + 1   = 2         
                   /    \
                 /        \
               /            \
             /                \
           /                    \
 maxDepth('4') = 1     maxDepth('5') = 1

Recently I learned the algorithm of finding the max depth of a tree, which is

  1. return 0 if it is a leaf
  2. Get the max of max depths of left and right subtrees and add 1 to it for the current node. max_depth = max(max dept of left subtree,
    max depth of right subtree) + 1

However, for the above graph, if our tree is:

1
    2
    3
      4
      5

Is the max depth of right subtree suppose to equal to 0 based on the algorithm? Also, the max depth of node 4 and 5 suppose to be 0, right? Please let me know which part of my reasoning is wrong.

1
tree

1 Answers

1
votes

maxDepth(3) , maxDepth(4) and maxDepth(5) should be zero as they are leaf according to the algorithm.

                                 1
                              /    \
                            /         \
                          /             \
                        /                 \
                      /                     \
                     2                       3
                   /   \
                 /       \
               /           \
             /               \
           /                  \
          4                    5

maxDepth(3) = maxDepth(4)  = maxDepth(5) = 0
maxDepth(2) = max(maxDepth(4), maxDepth(5)) + 1 = max(0, 0)+1 = 1
maxDepth(1) = max(maxDepth(2), maxDepth(3)) + 1 = max(1, 0)+1 = 2