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?:confused: :confused:

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.

Thank you!

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;
}

---

Ah..it seems to be..