Count number of leaf nodes in Binary Search Tree
#include<stdio.h>
#include<stdlib.h>
struct BST
{
int
data;
struct
BST *lchild;
struct
BST *rchild;
};
typedef struct BST * NODE;
int leaf=0;
NODE get_node()
{
NODE
temp;
temp
= (NODE) malloc(sizeof(struct BST));
temp->lchild
= NULL;
temp->rchild
= NULL;
return
temp;
}
void insert(NODE root, NODE newnode)
{
if
(newnode->data < root->data)
{
if
(root->lchild == NULL)
root->lchild
= newnode;
else
insert(root->lchild,
newnode);
}
if
(newnode->data > root->data)
{
if
(root->rchild == NULL)
root->rchild
= newnode;
else
insert(root->rchild,
newnode);
}
}
int leaf_nodes(NODE root)
{
if(root
== NULL)
return
0;
if(root->lchild
== NULL && root->rchild==NULL)
leaf++;
leaf_nodes(root->lchild);
leaf_nodes(root->rchild);
return
leaf;
}
void main()
{
int val, i,n, ln;
NODE
root = NULL, newnode;
printf("\nEnter the
number of elements: ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
newnode
= get_node();
printf("\nEnter
The node value: ");
scanf("%d",
&val);
newnode->data = val;
if
(root == NULL)
root
= newnode;
else
insert(root,
newnode);
}
ln = leaf_nodes(root);
printf("\nTotal number
of leaf nodes is: %d", ln);
}
Output:
Enter the number of elements: 12
Enter The node value: 6
Enter The node value: 9
Enter The node value: 5
Enter The node value: 2
Enter The node value: 8
Enter The node value: 15
Enter The node value: 24
Enter The node value: 14
Enter The node value: 7
Enter The node value: 8
Enter The node value: 5
Enter The node value: 2
Total
number of leaf nodes is: 4
