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

Binary Search Tree (BST) is an important data structure in C programming. In this program, we will learn how to count leaf nodes and total nodes in a BST using simple functions.

---

📝 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.

---

🌳 What is a Binary Search Tree?

A Binary Search Tree (BST) is a binary tree where:

• Left child contains values smaller than the root.
• Right child contains values greater than the root.

---

💡 Logic (Simple Steps)

1️⃣ To Count Total Nodes

• If tree is empty → return 0.
• Otherwise:Total Nodes = 1 + nodes in left subtree + nodes in right subtree

2️⃣ To Count Leaf Nodes

• If tree is empty → return 0.
• If node has no left and right child → it is a leaf node → return 1.
• Otherwise:Leaf Nodes = leaf in left subtree + leaf in right subtree

---

💻 Source Code (Student Friendly)

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

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

// Create new node
struct node* create(int data)
{
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = data;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}

// Insert into BST
struct node* insert(struct node* root, int data)
{
    if(root == NULL)
        return create(data);

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

    return root;
}

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

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

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

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

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

    printf("Enter values:\n");
    for(i = 0; i < n; i++)
    {
        scanf("%d", &value);
        root = insert(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 values:
10
5
15
3
7
Total number of nodes: 5
Number of leaf nodes: 3

---

🎓 Viva Questions with Answers

1. What is a leaf node?

A node with no left and right child is called a leaf node.

2. What is a Binary Search Tree?

A tree where left child is smaller and right child is greater than the root.

3. What is the base condition in recursion?

When the root is NULL.

4. What is the maximum number of leaf nodes in a binary tree?

At most (n+1)/2 where n is total nodes.

5. What is the time complexity of counting nodes?

O(n), because every node is visited once.