C Program to Find the Height of a Binary Tree

Introduction

The height of a binary tree is defined as the number of edges on the longest path from the root to a leaf node. It can also be seen as the number of levels in the tree minus one. If the tree is empty, its height is considered to be -1. For a tree with only one node (the root), the height is 0.

Example:

• Tree Structure:

       1
      / \
     2   3
    / \
   4   5
  

• Height of the Tree: 2

Problem Statement

Create a C program that:

• Constructs a binary tree.
• Calculates the height of the binary tree.
• Outputs the height of the tree.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output and memory allocation functions.
2. Define the Structure for a Tree Node: Each node will contain a data value and pointers to its left and right children.
3. Implement the Function to Calculate the Height: This function will recursively calculate the height of the binary tree.
4. Create a Main Function: Build a sample binary tree and calculate its height.

C Program to Find the Height of a Binary Tree

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new tree node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Function to find the height of the binary tree
int findHeight(struct Node* root) {
    if (root == NULL) {
        return -1; // If tree is empty, return -1
    } else {
        // Compute the height of each subtree
        int leftHeight = findHeight(root->left);
        int rightHeight = findHeight(root->right);

        // Use the larger one
        if (leftHeight > rightHeight) {
            return (leftHeight + 1);
        } else {
            return (rightHeight + 1);
        }
    }
}

int main() {
    // Creating a sample binary tree
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    // Find the height of the binary tree
    int height = findHeight(root);
    printf("The height of the binary tree is: %d\n", height);

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Structure for a Tree Node

• The struct Node defines a node of the binary tree, which contains an integer data and pointers to its left and right children.

Function to Create a New Tree Node

• The newNode function creates a new node with the given data, initializes its left and right pointers to NULL, and returns the pointer to the new node.

Function to Find the Height of the Binary Tree

• The findHeight function recursively calculates the height of the binary tree.
• If the tree is empty (i.e., root == NULL), it returns -1.
• Otherwise, it recursively calculates the height of the left and right subtrees.
• The height of the tree is the greater of the two subtree heights plus one.

Main Function

• The main function constructs a sample binary tree and calls the findHeight function to calculate and print the height of the tree.

Output Example

Example Output:

The height of the binary tree is: 2

Example Output (Different Tree):

If the binary tree is modified, for example:

       10
      /  \
     20   30
    /
   40

The height of the tree will be:

The height of the binary tree is: 2

Conclusion

This C program demonstrates how to calculate the height of a binary tree using a recursive approach. The height of a binary tree is a fundamental concept in tree-based data structures, and this program provides a practical example of how to implement it in C programming.