C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Binary Search Tree — Counting Total Nodes and Internal Nodes of BST

The Tree Properties section by adding programs to count:

  1. Total Nodes — every node in the BST.
  2. Internal Nodes — nodes that are not leaves (i.e., they have at least one child).

These are important analytical properties, often used to evaluate tree size, structure, and efficiency in data storage.

 Binary Search Tree — Counting Total & Internal Nodes

Concept Overview

Property

Description

Total Nodes

The total number of nodes in the tree.

Leaf Nodes

Nodes with no children.

Internal Nodes

Nodes that are not leaves (they have 1 or 2 children).

 Logic Summary

Count Total Nodes

Recursive Formula:

total_nodes = 1 + count(left_subtree) + count(right_subtree)

Count Internal Nodes

Recursive Formula:

if node == NULL → 0 

if (node->left == NULL && node->right == NULL) → 0 

else → 1 + count(internal_left) + count(internal_right)

 

C Program: Binary Search Tree - Counting Total 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;


}


 


// Function to count total nodes in BST


int countTotalNodes(struct Node* root) {


    if (root == NULL)


        return 0;


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


}


 


// Function to count internal (non-leaf) nodes


int countInternalNodes(struct Node* root) {


    if (root == NULL)


        return 0;


 


    if (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 totalNodes = countTotalNodes(root);


    int internalNodes = countInternalNodes(root);


 


    printf("Total Number of Nodes: %d\n", totalNodes);


    printf("Number of Internal Nodes: %d\n", internalNodes);


 


    return 0;


}

Output

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

Visual Representation

BST Structure:

        50

       /  \

     30    70

    / \    / \

  20  40  60  80

Node Type

Nodes

Count

Internal Nodes

50, 30, 70

3

Leaf Nodes

20, 40, 60, 80

4

Total Nodes

7

7

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

 Complexity Analysis

Operation

Time Complexity

Space Complexity

Total Node Count

O(n)

O(h)

Internal Node Count

O(n)

O(h)

n = total number of nodes, h = height of the tree.

 Key Points

  • Internal Nodes are all nodes except leaves.
  • These counts help determine tree density and balance.
  • Recursive structure mirrors divide-and-conquer pattern.
  • These are foundational metrics for higher-level operations (like tree balancing and compression).

 

Previous
Next