What happens to the variables at each stage of this recursive function?

Question

    public static int findHeight(Tree root) {
    int leftHeight, rightHeight;

    if (root == null) {
        return 0;
    }

    leftHeight = 1 + findHeight(root.left);
    rightHeight = 1 + findHeight(root.right);

    return leftHeight > rightHeight ? leftHeight : rightHeight;
}

My confusion here is for the variables leftHeight and rightHeight. What exactly is being added for the recursive call on this line?

 leftHeight = 1 + findHeight(root.left);

findHeight(root.left) does not return any value at that point so what addition will take place there? Or does it sum up the leftHeight for each recursive call? If so, how does that work?

"findHeight(root.left) does not return any value at that point so what addition will take place there? " - `findHeight` will return _eventually_ . That's when the addition will take place and result will be returned (so that caller can also return). — Sergio Tulentsev, Sep 13 '17 at 15:17
Duplicate of [Understanding how recursive functions work](https://stackoverflow.com/questions/25676961/understanding-how-recursive-functions-work). It appears to be not so much a problem with understanding this specific example as it is a problem with understanding recursion as a whole. — Bernhard Barker, Sep 13 '17 at 16:08

score 0 · Answer 1 · answered Sep 13 '17 at 15:19

I always recommend sitting with a paper and pen when coding something, it helps to lay down your logic.

For the above code snippet, let's consider an example as below:-

Now when call to this tree looks like

-> findHeight(3) -> findHeight(2) -> findHeight(1)
               \-> findHeight(4)

Now have a clear look, 
findHeight(1) will return 1;
findHeight(2) will return 1 + findHeight(1) = 2
findHeight(4) will return 1 + 0 (NULL) = 1
findHeight(3) will return 1 + max(2,1) = 3

Hope this helps you understand the recursion flow.

What happens to the variables at each stage of this recursive function?

1 Answers1