C Program to Count Leaf Nodes and Total Nodes in a Binary Search Tree (BST)

A Binary Search Tree (BST) is a binary tree where the left subtree contains values less than the node and the right subtree contains values greater than the node. In this program, we implement two functions:

1. Count leaf nodes (nodes with no children).
2. Count total number of nodes in the BST.

---

📝 Problem Statement

B) Write a C Program to implement the following functions on Binary Search Tree:

• To count leaf nodes.
• To count total number of nodes.

---

💡 Logic (Simple Steps)

🔹 Create BST

1. Define a node structure with data, left, and right pointers.
2. Insert nodes recursively based on BST property:
   • If value < current node → go to left subtree.
   • If value > current node → go to right subtree.

🔹 Count Leaf Nodes

1. If node is NULL → return 0.
2. If node has no left and right children → return 1.
3. Otherwise → recursively count leaf nodes in left and right subtrees.

🔹 Count Total Nodes

1. If node is NULL → return 0.
2. Otherwise → 1 + count nodes in left subtree + count nodes in right subtree.

---

💻 Source Code (Student-Friendly)

#include <stdio.h>
#include <stdlib.h>

// Node structure
struct node
{
    int data;
    struct node* left;
    struct node* right;
};

// Function to create a new node
struct node* createNode(int value)
{
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = value;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}

// Function to insert node in BST
struct node* insertBST(struct node* root, int value)
{
    if(root == NULL)
        return createNode(value);

    if(value < root->data)
        root->left = insertBST(root->left, value);
    else if(value > root->data)
        root->right = insertBST(root->right, value);

    return root;
}

// Function to count leaf nodes
int countLeafNodes(struct node* root)
{
    if(root == NULL)
        return 0;

    if(root->left == NULL && root->right == NULL)
        return 1;

    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

// Function to count total nodes
int countTotalNodes(struct node* root)
{
    if(root == NULL)
        return 0;

    return 1 + countTotalNodes(root->left) + countTotalNodes(root->right);
}

int main()
{
    struct node* root = NULL;
    int n, value, i;

    printf("Enter number of nodes: ");
    scanf("%d", &n);

    for(i = 0; i < n; i++)
    {
        printf("Enter value for node %d: ", i+1);
        scanf("%d", &value);
        root = insertBST(root, value);
    }

    printf("Total number of nodes: %d\n", countTotalNodes(root));
    printf("Number of leaf nodes: %d\n", countLeafNodes(root));

    return 0;
}

---

🖥️ Sample Output

Enter number of nodes: 5
Enter value for node 1: 50
Enter value for node 2: 30
Enter value for node 3: 70
Enter value for node 4: 20
Enter value for node 5: 40
Total number of nodes: 5
Number of leaf nodes: 3

Explanation:
Leaf nodes are 20, 40, and 70. Total nodes = 5.

---

🎓 Viva Questions with Answers

1. What is a Binary Search Tree (BST)?

A binary tree where left subtree < node < right subtree for every node.

2. What is a leaf node?

A node with no left or right children.

3. How do you count total nodes?

1 + count of nodes in left subtree + count of nodes in right subtree.

4. Why recursion is used here?

Because tree traversal naturally follows a recursive structure.

5. What is the time complexity of inserting in BST?

O(h), where h = height of the BST. In worst case (skewed tree) O(n).

---

✅ Conclusion

This C program is student-friendly and demonstrates how to:

• Create a Binary Search Tree
• Count leaf nodes
• Count total nodes

It is important for practical exams and helps students understand recursion, tree traversal, and BST properties clearly.