CODEWITHSUNDEEP
javarecursion
Daisy
Daisy

Reputation: 31

How to calculate the number of recursive calls in Java?

I was using the below given method to calculate height of a binary tree,

int height(Node root)
{
    if (root == null)
       return 0;
    else
    {
        int lheight = height(root.left);
        int rheight = height(root.right);

        if (lheight > rheight)
            return(lheight+1);
        else return(rheight+1); 
    }
}

This returns lheight = 2. Initially I thought that lheight increments by 1 on each recursive call to height(root.left). But then I added a printf statement and ran it again,

int height(Node root)
{
    if (root == null)
       return 0;
    else
    {
        int lheight = height(root.left);
        System.out.print(lheight);
        int rheight = height(root.right);

        if (lheight > rheight)
            return(lheight+1);
        else return(rheight+1); 
    }
}

The printf statement printed this 0 1 0 2 0. How is the value of lheight changing on each recursive call? I am not looking for a new solution. I know this can be done in many ways. I just want to understand what is going on in this code snippet. Here is the binary tree image link. Binary tree

Upvotes: 2

Views: 1454

Answers (5)

Jay Patel
Jay Patel

Reputation: 1

Take this for example

        1

      /   \
    2      3
  /  \
4     5

First, 1 will pass its left [height(root.left)] so 2 will be called.Then 2 will pass its left so 4 will be called.Now 4 will call its left.

since 4 don't have any left it will pass null or 0 to lheight.So this time the code goes to next step ie to function [ height(root.right) ].

For the right of 4, we have null so 0 will be returned to rheight. Now with help of [ return(rheight+1); ] function, value 1 will be passed to calling the function 2.

so 2 will have lheight as 1.Now 2 will now call its right.And so on the loop continues and 2 will have two values l=1 and r= 1 and will return 1+1=2 to its calling function i.e 1 .

the right of 1 is called and it will return 1 with the same loop like before. And finally, we have l=2 and r=1. Therefore, our final value will be [lheight+1]=3. so the height of a tree is 3

Upvotes: 0

HomerPlata
HomerPlata

Reputation: 1787

Pass in count as a parameter to your method, initially set at 0 or 1 (depending on your preference), and then increase it each time you recursively call the method.

EDIT: Being honest, I've not tested this code, so I can't figure out how you are supposed to be changing the height values. Feels like this will be infinitely recursive.

Anyway, here is the basic idea of tracking recursion count:

int height(Node root, int lCount, int rCount)
{
    if (root == null){
       return 0;
    }
    else {
        int lheight = height(root.left, lCount + 1, rCount);
        int rheight = height(root.right, lCount, rCount + 1);

        if (lheight > rheight){
            return(lheight);
        }
        else return(rheight); 
    }
}

You initialise the method call with height(root, 0, 0) and the very last execution of the L and R "branches" of execution should yield the respective totals.

Upvotes: 1

EmLe49
EmLe49

Reputation: 69

you can create a global variable that is increased every time that the function call himself

int i;   //it has to be initialized with 0 


int height(Node root)
{
    if (root == null)
        return 0;
    else
    {
         i++;
         int lheight = height(root.left);
         printf("%d ", lheight);
         i++;
         int rheight = height(root.right);

         if (lheight > rheight)
             return(lheight);
         else return(rheight); 
     }
 }

Upvotes: -1

Deb S
Deb S

Reputation: 544

Do something like this -

int height(Node root)
{
    if (root == null)
       return 0;
    else
    {
        return 1+ Math.max(height(root.left),height(root.right));
    }
}

To calculate height call like this 

int height = height(root); //this is the height not inside the function

I have not compiled it - but this is the way to get the height of a tree (c/c++/java/..)

Upvotes: 1

Swapan Shaw
Swapan Shaw

Reputation: 233

The height of a tree is max of the height of it left sub tree and height of right sub tree. So If you see your code then it is recursively calculating the height of left and right sub tree and checking which is max. If you realy want to visualize it. make tree structure of the called method. You can easy visualise it.

Upvotes: 0

Related Questions