C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Binary Search Tree — Counting Total Number of Nodes, Leaf Nodes, and Internal Nodes

This helps analyze the structure and density of a tree — key for understanding balance, memory usage, and traversal complexity.

Binary Search Tree — Node Counting

Concept Overview

A Binary Search Tree (BST) contains three categories of nodes:

  1. Total Nodes:
    All nodes present in the tree.
  2. Leaf Nodes:
    Nodes with no children (both left and right are NULL).
  3. Internal Nodes:
    Nodes that have at least one child.

Recursive Logic Summary

1. Count Total Nodes

int countTotalNodes(struct Node* root) {

    if (root == NULL)

        return 0;

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

}

 

2. 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);

}

 

3. Count Internal Nodes

int countInternalNodes(struct Node* root) {

    if (root == NULL || (root->left == NULL && root->right == NULL))

        return 0;

    return 1 + countInternalNodes(root->left) + countInternalNodes(root->right);

}

 

C Program: Binary Search Tree - Counting Total Number of Nodes, Leaf Nodes, and Internal Nodes

C 
#include <stdio.h>


#include <stdlib.h>


 


// Structure for BST Node


struct Node {


    int data;


    struct Node *left, *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 = newNode->right = NULL;


    return newNode;


}


 


// Function to insert a node in BST


struct Node* insert(struct Node* root, int value) {


    if (root == NULL)


        return createNode(value);


 


    if (value < root->data)


        root->left = insert(root->left, value);


    else if (value > root->data)


        root->right = insert(root->right, value);


 


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


}


 


// Count internal nodes


int countInternalNodes(struct Node* root) {


    if (root == NULL || (root->left == NULL && root->right == NULL))


        return 0;


    return 1 + countInternalNodes(root->left) + countInternalNodes(root->right);


}


 


// Inorder traversal for verification


void inorder(struct Node* root) {


    if (root != NULL) {


        inorder(root->left);


        printf("%d ", root->data);


        inorder(root->right);


    }


}


 


int main() {


    struct Node* root = NULL;


 


    // Construct BST


    root = insert(root, 50);


    root = insert(root, 30);


    root = insert(root, 70);


    root = insert(root, 20);


    root = insert(root, 40);


    root = insert(root, 60);


    root = insert(root, 80);


 


    printf("Inorder Traversal of BST: ");


    inorder(root);


    printf("\n");


 


    int total = countTotalNodes(root);


    int leaves = countLeafNodes(root);


    int internal = countInternalNodes(root);


 


    printf("Total Nodes: %d\n", total);


    printf("Leaf Nodes: %d\n", leaves);


    printf("Internal Nodes: %d\n", internal);


 


    return 0;


}

Output

 
OUTPUT :
Inorder Traversal of BST: 20 30 40 50 60 70 80
Total Nodes: 7
Leaf Nodes: 4
Internal Nodes: 3

Visualization

        50

       /  \

     30    70

    / \    / \

  20  40  60  80

Type

Nodes

Count

Leaf Nodes

20, 40, 60, 80

4

Internal Nodes

50, 30, 70

3

Total Nodes

All nodes

7

Check: Total = Leaf + Internal → 7 = 4 + 3

Complexity Analysis

Operation

Time Complexity

Space Complexity

Count Total Nodes

O(n)

O(h)

Count Leaf Nodes

O(n)

O(h)

Count Internal Nodes

O(n)

O(h)

Where:

  • n = total number of nodes
  • h = height of the tree

Key Takeaways

  • Counting nodes helps analyze tree density and structure balance.
  • Leaf nodes represent endpoints in recursion and traversal.
  • Internal nodes drive most recursive and branching logic.
  • These metrics are used in tree visualization, balance checking, and memory usage analysis.
  • The recursive approach ensures a single traversal can compute all three counts efficiently.

 

Previous
Next