Recursion in binary tree

[agoswami]

Hi,
I was writing program for binary tree and trying to find the leght of binary tree through max_tree function.This code compile and work fine but I coudlnot
understand the max_tree function which is using recursion.

The basis question which I have max_tree recursion function about base condition.base condition is returning zero but how is it going to calculate height of the tree. Please find the code below for more info.

I have given only max_tree function if require I can provide complete code also.
Please ignore cout I was using for debug purpose

int tree::max_tree(node *root)
{
    int lft,rht;
    if(root==NULL)
       return 1;
    else
    {
      cout<<"root->data :"<<root->data<<endl;
      lft=max_tree(root->left);
      cout<<"the lft is:"<<lft<<endl;
      cout<<"root->data :"<<root->data<<endl;
      rht=max_tree(root->right);
      cout<<"root->data :"<<root->data<<endl;
      cout<<"the rht is:"<<rht<<endl;
      if(lft>rht)
         return lft+1;
      else
         return rht+1;
     }

[agoswami]

Sorry I got the thing it i s returning from the if and else block whic is collection 1 into max_tree function

[Gaminic]

I don't think that's correct; line 5 should return 0.

If any subtree rooted at X has no children, then its size is 1. Using this code, it would return 2, as a max_tree(NULL) still returns 1.


Anyway, the logic is pretty simple. The height of a subtree is the amount of tiers (levels) it contains. For a leaf node, this is 1, because it only has one tier: the 0-tier (or root-tier). By definition, each "downward path" in the tree ends in a leaf node, thus the height of a subtree is the length of the maximum size "downward path".

At each node, a new subtree starts, with the current node as a root. The height of this subtree is 1 (itself) plus the biggest size of the left and right subtree.

Thus, the logic does this: walk down until a leaf is found, then walk up and add 1 for each tier encountered. Discard the shortest subtree.

[agoswami]

hmm thanks for reply.. what I got understand from the code.

1. First reach the leaf node
2. fun call node->left as root which return zero becuase leaf does not have left node and return zero.

3. check the above condition for the right node and also return zero.

4. than it moves to if block for lft or rht is greater.

5. it add 1 with lft which become summation for the next recursion

[Gaminic]

Basically, yeah, with the exception that in 5), it adds 1 to the summation for the previous recursion. Remember that each execution of the function is called from a previous call to that function.