# Count Number of Leaf Nodes in a Binary Tree

+1 vote
443 views

Its a recursive function . We have to traverse the whole tree and at each node we will check if a node is without child then will increase the count.

Number of leaf node in the above tree - 3

Sample Code

struct node
{
int data;
struct node *lsubtree;
struct node *rsubtree;
};

struct node * create_node(int data)
{
struct node *new;

new = (struct node*)malloc(sizeof(struct node));
new->lsubtree = null;
new->rsubtree = null;
new->data = data;

return new;
}

{
{
}
{
}
{
}
}

struct node *search(int data, struct node *head)
{
{
{
}
{
}
else
{
}
}
else return null;
}

void preorder_traversal (struct node * root)
{
if (root != NULL) {
printf("%c ", root->data);
preorder_traversal(root->lsubtree);
preorder_traversal(root->rsubtree);
}
}

void inorder_traversal (struct node * root)
{
if (root != NULL) {
inorder_traversal(root->lsubtree);
printf("%c ", root->data);
inorder_traversal(root->rsubtree);
}
}

void postorder_traversal (struct node * root)
{
if (root != NULL) {
postorder_traversal(root->lsubtree);
postorder_traversal(root->rsubtree);
printf("%c ", root->data);
}
}

void count_leaf_node(struct node * root, int *count)
{
if (root == NULL)
{
return;
}
if (root->lsubtree == NULL && root->rsubtree == NULL)
{
*count = *count + 1;
}
count_leaf_node(root->lsubtree, count);
count_leaf_node(root->rsubtree, count);
}
posted Sep 24, 2014