Understanding how to calculate the depth of a Binary Tree

Question

I am going through the Career Cup guide as a crash course through basic CS principals and stuck on the example which calculates the minimum/maximum depth of a Binary Tree. Since this is the same problem I'm having with almost every example I thought I'd post a question here.

The instructions are to implement a method that will check to see if a tree is balanced. In order to do this, you need to compare the minimum depth with the maximum depth, and ensure their difference is no greater than 1. This principal is as straightforward as it gets. The method on line 15 is intended to do just that.

However, I do not understand what is going on in the return statements of each helper method (maxDepth and minDepth). How is a number being derived from either root.left or root.right? Does the Math.max function simply assume a 1 or a 0 is there a value/null node, or, since there is no value being specified (just the Node object), does Math.max(maxDepth(root.left), maxDepth(root.right) itself equal 0, thus incrementing the return value by 1 until both nodes are null?

If so is this the general process used to calculate the min/max depth of a tree:

minDepth = does the root have any children? yes = minDepth = 1, no = minDepth = 0 (if there is a root)

maxDepth = cycle through both branches until you find the leaf furthest from the root. Keep a counter going to determine the leaves.

1   public static int maxDepth(TreeNode root) {
2       if (root == null) {
3       return 0;
4       }
5       return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
6   }
7
8   public static int minDepth(TreeNode root) {
9       if (root == null) {
10          return 0;
11      }
12      return 1 + Math.min(minDepth(root.left), minDepth(root.right));
13  }
14
15  public static boolean isBalanced(TreeNode root){
16      return (maxDepth(root) - minDepth(root) <= 1);
17  }

Answer 1

maxDepth(root.left) returns the max depth of the left sub tree.
maxDepth(root.right) returns the max depth of the right sub tree.
The max of these two is the maximal sub tree depth.
Adding 1 for the root node, you get the max depth of the tree.

Suppose this is the tree :

            A
         B      C
       D   E   F   G
     H
   I

Just by looking at it you can see the max depth is 5 (formed by the path A-B-D-H-I) and the min depth is 3 (formed by several paths, for example A-C-G).

Now, the max depth is 1 (for the root A) + the max depth of the two sub trees.
The first sub tree, whose root is B has max depth 4 (B-D-H-I). The second sub tree, whose root is C has a max depth 2 (C-F).
max(4,2) = 4
Therefore the max depth of the entire tree is 1 + max(4,2) = 5.

If we use the letter in my sample tree to represent the sub-trees rooted in those nodes, we get :

maxDepth(A) = 1 + max(maxDepth(B) , maxDepth(C)) =
              1 + max(1 + max(maxDepth(D) , maxDepth(E)), 1 + max(maxDepth(F) , maxDepth(G)) =
              1 + max(1 + max(1+max(maxDepth(H),0) , 1+max(0,0)), 1 + max(1+max(0,0) , 1+max(0,0)) =
              1 + max(1 + max(1+max(1+max(maxDepth(I),0),0) , 1), 1 + 1) =
              1 + max(1 + max(1+max(1+max(1+max(0,0),0),0) , 1), 1 + 1) =
              1 + max(1 + max(1+max(1+max(1,0),0) , 1), 2) =
              1 + max(1 + max(1+max(2,0) , 1), 2) =
              1 + max(1 + max(3 , 1), 2) =
              1 + max(4, 2) =
              1 + 4 =
              5

Similarly, for calculating the min depth, you calculate the min depth of the two (left and right) sub-trees, take the minimum of the two, and add 1 for the root.

Answer 2

Well, it's a recursive function that checks both sides of the tree then compares the result with either max or min.

Pictures help.

       o  go left and right
     /    \
(+1)o      o(+1)       
    \       
     o(+1)   

So lets bring it back to the code.

return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));

the call stack would look something like this

// max return 2
- left +1                      
    // max return 1
    -left 0                    
    -right +1
       // max return 0
      -left  0                 
      -right 0
- right +1
    //max return 0
    -left 0
    -right 0

Min works essentially the same way.