stack frame on a binary tree traversal

Question

I am having a hard time understanding the stack frame picture of a binary tree traversal

I have this function to calculate the height of a binary tree starting with the root node

public static int height(TreeNode<String> t){
        if(t == null)
            return -1;
        int left = height(t.left);
        System.out.println("left " +left);
        int right = height(t.right);
        System.out.println("right " +right);

        if(left > right)
            return left + 1;
        else
            return right + 1;

    }

I have a binary tree setup as follows

             Root
            /    \
           A      B

The returned height value is 1 which is correct but I am having a hard time understanding the stack frame flow of the two recursive functions. What is the flow order like?

I get the following out values on my two print statements

left -1
right -1
left 0
left -1
right -1
right 0

Answer 1

Executions of height follow the tree shape in order.

height is called first on Root and then recursively on Root.left in line 4 and then again recursively on Root.left.left, which is null. At this point the last execution of height returns -1 and terminates. The remaining last execution assigns this to left and prints it.

This same execution nex calls height on Root.left.right. This is also null, so -1 is returned and printed, after which the if statement computes -1 + 1 == 0 and returns this.

We are now back to the call on Root.left, and the returned value 0 is assigned to left and is printed, whereupon the same execution calls height again and again on down to Root.right.left, which is null, so again -1 is printed.

You should see the pattern at this point.

Answer 2

left -1   A.left is null
right -1  A.right is null
left 0    Root.left is A
left -1   B.left is null
right -1  B.right is null
right 0   Root.right is B

But if you want a clearer picture you should probably code something like

public static int height(TreeNode<String> t){
  if(t == null)
    return -1;
  int left = height(t.left);
  System.out.println(t+" left "+left);
  int right = height(t.right);
  System.out.println(t+" right "+right);
  if(left > right)
    return left + 1;
   else
    return right + 1;
}

Answer 3

Not sure what exactly is your problem, but here it goes:

1) Initial call to height with root node

2) First recursive call to height with A node

3) Second recursive call to height with A.left (which is null)

4) First if statement fires, returns -1 - back to after the call in point 3)

5) First print statement - "left -1". Third recursive call to height with A.right (which is null)

6) if fires again, returns -1 - back to after the call in point 5)

7) Second print statement - "right -1".

8) left is -1 and right is -1, hence right + 1 is returned (0)- back to after the call in point 2)

9) Third print statement - "left 0".

10) Next recursive call of height with B node. Repeat steps 2-8 substituting B for A. Repeating this yields two print statements "left -1" and "right -1".

11) After getting back, right is 0 and thus the last print statement reads "right 0".

12) left is 0 and right is 0, hence right + 1 is returned