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