Recursion code flow for binary tree

Question

I am trying to understand this recursion program step-by-step as to what happens everytime the function gets called but want to make sure if the code flow that I think is correct or not.

    public static int checkHeight(TreeNode root) {
        if (root == null) {
            return 0; // Height of 0
        }

        /* Check if left is balanced. */
        int leftHeight = checkHeight(root.left);
        if (leftHeight == -1) {
            return -1; // Not balanced
        }
        /* Check if right is balanced. */
        int rightHeight = checkHeight(root.right);
        if (rightHeight == -1) {
            return -1; // Not balanced
        }

        /* Check if current node is balanced. */
        int heightDiff = leftHeight - rightHeight;
        if (Math.abs(heightDiff) > 1) {
            return -1; // Not balanced
        } else {
            /* Return height */
            return Math.max(leftHeightJ rightHeight) + 1;
        }
    }
    public static boolean isBalanced(TreeNode root)
    {
        if (checkHeight(root) == -1)
        {
            return false;
        }
        else
        {
            return true;
        }
    }

Example:

           1
        /     \
       2       3
    /    \   /
   4      5  6
 /
7

When the program runs and reaches the line checkHeight(root.left) it has now element to 2(root.left) so this get recursively called and the stack has executions paused like

|checkHeight(2)|

and then till it reaches the end of left most element it has the

|checkHeight(7)|
|checkHeight(4)|
|checkHeight(2)|

|checkHeight(7)| pops out with leftHeight = 0 rightHeight = 0.

when running |checkHeight(4)| -> leftHeight = 1 , rightHeight =0

|checkHeight(2)| -> leftHeight = 2, rightHeight=1(as it runs for |checkHeight(5)|)

Once this gets completed, it returns: Max(2,1)+1 = 3 which will be the value of leftHeight.

Is my understanding correct? Hopefully I did not confuse with the steps. Thanks in advance

What langauge is this written in, you might want to edit the tags to include that. — M Y
– M Y, Commented Jun 29, 2015 at 4:24
I think with current code you might have an infinite loop here. Not 100% sure... — M Y
– M Y, Commented Jun 29, 2015 at 4:26
I added the language. I haven't debugged the code yet going through the left substree step by step I havent come across the case where it will go for infinite loop. I will cross check. — Kar
– Kar, Commented Jun 29, 2015 at 5:06

Manish Kumar Sharma · Accepted Answer · 2015-06-29 04:54:41Z

1

Since you haven't asked a concrete question, which can be answered in terms of code, I can say this:

The key to recursion is not following every invocation and stick to the invocation maze, it is reading the code(for the recursive invocation) and believe what the recursive invocation is supposed to do, what it is supposed to do. Better be sure about the correctness of single invocation of what it is doing. Then you can directly jump through all the "similar" invocations till the end(like the 7 here)

The other thing is the fundamental rule, there must be a condition where the method returns-The Base case(To prevent the infinite looping)

Considering both these facts, I think you are going all right with the steps(I followed through invocations to be sure.)

Tip: You can always use breakpoints in debugging to check the whole procedure instead of going over manually. After all, that's what debugging is for.

edited Jun 29, 2015 at 4:54

answered Jun 29, 2015 at 4:49

Manish Kumar Sharma

13.5k11 gold badges66 silver badges110 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Kar Over a year ago

You are right indeed..just wanted to make sure if I got it right on the paper before debugging. Thanks for the information and verifying the correctness of the steps.

Collectives™ on Stack Overflow

Recursion code flow for binary tree

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related