Thread: Calculates the number of leaves

  1. #1
    Compiling
    Join Date
    Jun 2003
    Posts
    69

    Question 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. #2
    Registered User
    Join Date
    Sep 2003
    Posts
    23
    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. #3
    Compiling
    Join Date
    Jun 2003
    Posts
    69
    Thank you!

  4. #4
    Registered User
    Join Date
    Dec 2002
    Posts
    27
    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;
    }
    "Can i really learn this? If i cant, why bother?"

  5. #5
    Compiling
    Join Date
    Jun 2003
    Posts
    69
    Ah..it seems to be..

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with this compiler error
    By Evangeline in forum C Programming
    Replies: 7
    Last Post: 04-05-2008, 09:27 AM
  2. Finding a number within a number
    By jeev2005 in forum C Programming
    Replies: 2
    Last Post: 01-10-2006, 08:57 PM
  3. help with a source code..
    By venom424 in forum C++ Programming
    Replies: 8
    Last Post: 05-21-2004, 12:42 PM
  4. parsing a number
    By juancardenas in forum C Programming
    Replies: 1
    Last Post: 02-19-2003, 01:10 PM
  5. Random Number problem in number guessing game...
    By -leech- in forum Windows Programming
    Replies: 8
    Last Post: 01-15-2002, 05:00 PM