# Calculates the number of leaves

This is a discussion on Calculates the number of leaves within the C Programming forums, part of the General Programming Boards category; I want to calculate the number of leaves in a binary search tree. I think the code should be like ...

1. ## Calculates the number of leaves

I want to calculate the number of leaves in a binary search tree.
I think the code should be like this in the recursion way:
Code:
```int
Leaves(Tree T)
{
int LL, RL;
.......
LL = Leaves(T->Left);
RL = Leaves(T->Right);
return LL+RL;
}```
but what is the base case? It seems to be too many cases should be considered (such as "have a left subtree but no right subtree"), so the base case is not easy to write?

2. Here is my view of the problem:

For tree without any subtrees the result is one, because such a tree is a leaf. It's easy to find out whether the has some subtrees or not, for example
Code:
```if ((T->left == NULL) && (T->right == NULL))
return 1;```
And if the tree is not empty, the result is sum of results for subtrees:
Code:
`return Leaves(T->left) + Leaves(T->right);`
The recursion will end, because there is only a finite number of subtrees in a finite tree.
Maybe it will also be good to check whether the tree is not empty, I mean whether T != NULL.

3. Thank you!

4. Code:
```if ((T->left == NULL) && (T->right == NULL))
return 1;```
Dont you get wrong result with this code?
You should be counting up every time you visit a leave and when
the no leave exist, you return 0.

Like this:

Code:
```int
Leaves (
Tree   T)
{
if ( T != NULL )
return 1 + Leaves (T->left) + Leaves (T->right);
else
return 0;
}```

5. Ah..it seems to be..