Counting the number of the leaves in tree

[momotaro]

This is my code is it correct?:

int CountLeaves(Tree *root){
if (root == NULL) return 0;
else if (root -> left == NULL && root -> right == NULL) return 1;
else{
       CountLeaves(root -> left);
       CountLeaves(root -> right);
      }
}

THX!

[Ganon11]

In your else branch, you should be returning values; instead, you are just calling the function and doing nothing with the return values.

[momotaro]

is this one correct?

int CountLeaves(Tree *root){
int count = 0;
if (root){
           CountLeaves(root -> left);
           CountLeaves(root -> right);
           count++;
     return count;
          }
}

THX!

[momotaro]

this latter don't work either!!!! am realy stuck plz help!

[JosAH]

Think recursively again: if a tree is empty it has zero leaves; if a tree is a leaf,
well the tree has one leaf; otherwise count the number of leaves in the left
subtree plus the number of leaves in the right subtree.

kind regards,

Jos

ps. I don't understand your confusion here: all the questions you have posted
deal with trees and all the algorithms you have shown us all have an (almost)
identical recursive structure. Some of the algorithms are just perfect while
the others are totally incorrect. Did you copy the correct algorithms from a
textbook or what?

[momotaro]

thx for the hint!
concerning the accurency of my algos it is just because i dont know how to use the recrsion very well yet :)!
i' ve come up with this one for counting the leaves i hope it will be fine!

int CountLeaves(Tree *root){
int count;
if (root == NULL) return 0;
else{
       CountLeaves(root -> left);
       countLeaves(root -> right);
       count++;
       }
}

[JosAH]

thx for the hint!
concerning the accurency of my algos it is just because i dont know how to use the recrsion very well yet :)!
i' ve come up with this one for counting the leaves i hope it will be fine!

int CountLeaves(Tree *root){
int count;
if (root == NULL) return 0;
else{
       CountLeaves(root -> left);
       countLeaves(root -> right);
       count++;
       }
}

If the root is NULL you return 0 (zero) otherwise you don't return anything and
you discard the return values from your two recursive function calls.

The number of leaves is either 0 when the tree is empty, 1 when the tree is a
leaf itself, otherwise it's the number of leaves in the left subtree plus the
number of leaves in the right subtree.

hint: try to write that function without the 'count' variable; you don't need it.

kind regards,

Jos

[momotaro]

thx a lot this one should be perfect...i hope :)

int CountLeaves(Tree *root){
if (root == NULL) return 0;
else if (root -> left == NULL && root -> right == NULL) return 1;
else
      return( CountLeaves(root -> left) +
                CountLeaves(root -> right));
}

[JosAH]

thx a lot this one should be perfect...i hope :)

int CountLeaves(Tree *root){
if (root == NULL) return 0;
else if (root -> left == NULL && root -> right == NULL) return 1;
else
      return( CountLeaves(root -> left) +
                CountLeaves(root -> right));
}

Yep, that's it. You can get rid of that explicit leaf test (the else-if) at the
expensive of a bit more function calls and a temporary variable like this:

int CountLeaves(Tree* root) {
   if (root) {
      int temp= CountLeaves(root->left)+CountLeaves(root->right);
      return (temp == 0)?1:temp;
   }
   return 0;
}

kind regards,

Jos

[momotaro]

please can you explain me this line:

return (temp == 0)?1:temp;

thx! :)

[momotaro]

WAW it is realy a good one i understood it!!!!
thx a lot!