CODEWITHSUNDEEP
javarecursiontreebinary-tree
Kar
Kar

Reputation: 105

Recursion code flow for binary tree

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

Upvotes: 1

Views: 178

Answers (1)

Manish Kumar Sharma
Manish Kumar Sharma

Reputation: 13442

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.

Upvotes: 1

Related Questions