C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Binary Search Tree — Finding the Height (or Depth) of a BST

Binary Search Tree — Height / Depth Calculation

Concept Overview

The height (or depth) of a tree is a measure of how "tall" the tree is.
It is defined as:

Height of a tree = number of edges in the longest path from the root to a leaf node.

If we count nodes instead of edges, it’s sometimes defined as:

Height = number of nodes in the longest path – 1

Key Points

  • Height of an empty tree = 0
  • Height of a leaf node = 1
  • Height of a tree = 1 + max(height(left subtree), height(right subtree))

Recursive Formula

int height(struct Node* root) {

    if (root == NULL)

        return 0;

    else {

        int leftHeight = height(root->left);

        int rightHeight = height(root->right);

 

        return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;

    }

}

 

C Program: Binary Search Tree - Finding the Height (or Depth) of a BST

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


}


 


// Recursive function to find height of BST


int height(struct Node* root) {


    if (root == NULL)


        return 0;


 


    int leftHeight = height(root->left);


    int rightHeight = height(root->right);


 


    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;


}


 


// 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 h = height(root);


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


 


    return 0;


}

Output

 
OUTPUT :
Inorder Traversal of BST: 20 30 40 50 60 70 80
Height of the BST: 3

Visualization

BST structure:

        50

       /  \

     30    70

    / \    / \

  20  40  60  80

Longest path (root to leaf):
50 → 30 → 20 (or 50 → 70 → 80)

→ Number of edges = 2
→ Number of nodes = 3

Hence, Height = 3

Complexity Analysis

Operation

Time Complexity

Space Complexity

Find Height

O(n)

O(h)
  • Every node is visited once.
  • Recursion depth = height of the tree.

Key Points

  • Height shows how balanced or skewed a tree is.
  • A perfectly balanced BST has height ≈ log₂(n).
  • A completely skewed BST (like a linked list) has height = n.
  • Height is used in balancing algorithms (like AVL and Red-Black Trees).
  • It’s also crucial for tree traversal efficiency and recursive complexity analysis.

 

Previous
Next