Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1685
  • Last Modified:

Finding leaves in a Binary Search Tree

Hello,

I need a method that will find the # of leaves in a Binary SEarch Tree -- I'm using a Red Black Tree.  I need it ASAP! Thanks!

-Taylor
0
NeedlessKane
Asked:
NeedlessKane
  • 2
2 Solutions
 
dennismvCommented:
just a thought ...
traverse the tree using whichever method you like.  For each node you visit, check if it has any children.  If not, count it as a leaf, because it is.

At the end of the algorithm, you will have the total number of children.  This code works for any tree.

For example for a binary tree you can do in-order traversal using a recursive function

This is pseudocode adapted from a C/C++ version at http://datastructures.itgo.com/trees/traversal.htm

inorder(struct NODE curr)
{
  if(curr->left != NULL)
    inorder(curr->left);
    if (both leaves are null)
      count++;

  if(curr->right != NULL)
    inorder(curr->right);
}

You call this function by passing it root, i.e.
inorder(root);
Also have a global or some such variable called count.  Initialize it to 0.  It will be incremented by 1 for every leaf.
0
 
baboo_Commented:
Or to do it without using a global variable:

public int numLeaves( Node n )
{
    // if we've been given a null reference, return 0
    if ( n == null )
        return 0;

    // if we're at a leaf, return 1
    if( n.hasLeftChild() == false && n.hasRightChild() == false )
        return 1;

    // if we're not at a leaf, count all the leaves in this subtree and return that value
    if ( n.hasLeftChild() && n.hasRightChild() )
        return numLeaves( n.leftChild ) + numLeaves( n.rightChild );
}

baboo_
0
 
baboo_Commented:
Oops.  Use this instead of the above...  

public int numLeaves( Node n )
{
    // if we've been given a null reference, return 0
    if ( n == null )
        return 0;

    // if we're at a leaf, return 1
    if( n.hasLeftChild() == false && n.hasRightChild() == false )
        return 1;

    // if we're not at a leaf, count all the leaves in this subtree and return that value
    else
        return numLeaves( n.leftChild ) + numLeaves( n.rightChild );
}

baboo_
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now