C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Binary Search Tree — Height and Leaf Node Count of BST

Height Calculation and Leaf Node Counting in a Binary Search Tree (BST) — two fundamental analytical operations that follow naturally after traversals.

These are frequently asked in interviews and used in tree analysis algorithms.

 

Binary Search Tree — Height & Leaf Node Count

Concept Overview

Property

Description

Height of BST

The number of edges on the longest path from root to a leaf. (If counting nodes, it’s +1.)

Leaf Node

A node with no left or right child (i.e., both are NULL).

 Logic Summary

Height Calculation (Recursive)

  • Base Case: If node is NULL, height = 0.
  • Recursive Case:
  • height = 1 + max(height(left_subtree), height(right_subtree))

Leaf Node Count (Recursive)

  • Base Case: If node is NULL, count = 0.
  • If node is leaf (left == NULL && right == NULL), count = 1.
  • Else:
  • count = count(left_subtree) + count(right_subtree)

 

C Program: Binary Search Tree - Height and Leaf Node Count

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 into 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 calculate height of BST


int height(struct Node* root) {


    if (root == NULL)


        return 0;


 


    int leftHeight = height(root->left);


    int rightHeight = height(root->right);


 


    if (leftHeight > rightHeight)


        return leftHeight + 1;


    else


        return rightHeight + 1;


}


 


// Function to count number of 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);


}


 


// 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: ");


    inorder(root);


    printf("\n");


 


    int treeHeight = height(root);


    int leafCount = countLeafNodes(root);


 


    printf("Height of the BST: %d\n", treeHeight);


    printf("Number of Leaf Nodes: %d\n", leafCount);


 


    return 0;


}

Output

 
OUTPUT :
Level Order Traversal: 50 30 70 20 40 60 80Inorder Traversal: 20 30 40 50 60 70 80
Height of the BST: 3
Number of Leaf Nodes: 4

Visual Representation

For the BST:

        50

       /  \

     30    70

    / \    / \

  20  40  60  80

  • Height = 3
    (Longest path: 50 → 30 → 20 or 50 → 70 → 80 → 3 nodes, 2 edges → height = 3 levels)
  • Leaf Nodes = 4 → {20, 40, 60, 80}

 Complexity Analysis

Operation

Time Complexity

Space Complexity

Height Calculation

O(n)

O(h)

Leaf Node Counting

O(n)

O(h)

Here, n = number of nodes, h = height of tree.

 Key Takeaways

  • Height represents tree balance — smaller height = better performance.
  • Leaf nodes often represent terminal data elements.
  • These recursive functions are classic examples of divide-and-conquer tree algorithms.
  • Used in evaluating tree balance, completeness, and search performance.

 

Previous
Next