In a binary search tree, a node which contains blank left and right children’s that particular node is called as a leaf node in a tree. Here We are going give a c program for finding the number of leaf nodes in a tree.
In a c Program we explained recursively how to find leaf nodes.
#include
typedef struct node
{
int value;
int visited;
int bf;
struct node *right;
struct node *left;
}mynode;
void count_leaf(mynode *node)
{
if(node == NULL)
return 0;
if(node->left == NULL && node->right==NULL)
return 1;
else
return getLeafCount(node->left)+
getLeafCount(node->right);
}
}
Complexity of the program will be same as of tree traversal.
If any one can write non recursive program . Please do post.
*******************************************************************************************************
JAVA CODE FOR COUNTING LEAFNODES
*******************************************************************************************************
static int t=0;
public static bnode totalLeafNode(bnode root)
{
if(root==null)
{
return root;
}
if(root.left==null && root.right==null)
{
t++;
System.out.println(“t = “+t);
}
else
{
totalLeafNode(root.left);
totalLeafNode(root.right);
}
return root;
}