C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Binary Search Tree — Counting Left and Right Subtree Nodes

Tree balance analysis — by counting the number of nodes in the left and right subtrees of the root (or any given node).

This helps measure how balanced the tree is, a concept that’s foundational for AVL trees, Red-Black trees, and other balanced tree structures.

Binary Search Tree — Counting Left and Right Subtree Nodes

Concept Overview

For any given root node:

  • Left Subtree Nodes → All nodes present in the left child’s subtree.
  • Right Subtree Nodes → All nodes present in the right child’s subtree.

By comparing the counts, we can determine whether the tree is balanced or skewed.

Logic Summary

Recursive approach:

int countNodes(struct Node* root) {

    if (root == NULL)

        return 0;

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

}

Then for the root:

int leftCount = countNodes(root->left);

int rightCount = countNodes(root->right);

 

C Program: Binary Search Tree - Counting Left and Right Subtree 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 a subtree


int countNodes(struct Node* root) {


    if (root == NULL)


        return 0;


    return 1 + countNodes(root->left) + countNodes(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 leftCount = countNodes(root->left);


    int rightCount = countNodes(root->right);


 


    printf("Number of Nodes in Left Subtree: %d\n", leftCount);


    printf("Number of Nodes in Right Subtree: %d\n", rightCount);


 


    if (leftCount == rightCount)


        printf("The tree is perfectly balanced at the root.\n");


    else if (leftCount > rightCount)


        printf("The tree is left-heavy.\n");


    else


        printf("The tree is right-heavy.\n");


 


    return 0;


}

Output

 
OUTPUT :
Inorder Traversal of BST: 20 30 40 50 60 70 80
Number of Nodes in Left Subtree: 3
Number of Nodes in Right Subtree: 3
The tree is perfectly balanced at the root.

Visual Representation

For the BST:

        50

       /  \

     30    70

    / \    / \

  20  40  60  80

Subtree

Nodes

Count

Left Subtree

30, 20, 40

3

Right Subtree

70, 60, 80

3

Total

6 (excluding root)

6

Since both sides have equal nodes, the tree is balanced at the root.

Complexity Analysis

Operation

Time Complexity

Space Complexity

Counting Nodes

O(n)

O(h)

Balance Check

O(n)

O(h)

Here:

  • n = number of nodes
  • h = height of the tree (for recursion)

Key Points

  • Comparing left and right subtree sizes gives insight into tree balance.
  • Perfectly balanced trees improve search and insertion time from O(n) → O(log n).
  • The logic of countNodes() forms the base for AVL and Red-Black Tree rotations.
  • You can extend this logic to compute Balance Factor = |leftCount - rightCount| for each node.

 

Previous
Next