C Program to Find the Height of Tree using Recursion

This C program illustrates the computation of the height of a binary tree using a recursive algorithm.

In computer science, a tree is a widely used data structure that represents a hierarchical structure. A binary tree is a type of tree where each node has at most two child nodes, referred to as the left child and the right child. The height of a binary tree is the maximum number of edges between the root node and any leaf node. To find the height of a binary tree we are using recursion, we can use a recursive algorithm.

Problem Statement

Problem: Write a C program to find the height of a binary tree using recursion.

Input: The input to the program is a binary tree, represented as a collection of nodes. Each node has an integer value and pointers to its left and right child nodes. The binary tree is not necessarily balanced.

Output: The program should calculate and output the height of the binary tree.

C Program to Find the Height of Tree using Recursion

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

// Definition of a binary tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

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

// Recursive function to calculate the height of a binary tree
int height(struct Node* root) {
    // Base case: an empty tree has height 0
    if (root == NULL)
        return 0;

    // Recursive calls to find the height of the left and right subtrees
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);

    // Return the maximum height between the left and right subtrees, plus 1 for the current node
    return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
}

int main() {
    // Constructing a binary tree
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);

    // Calculate and print the height of the binary tree
    int treeHeight = height(root);
    printf("Height of the tree is: %d\n", treeHeight);

    return 0;
}

How it Works

The program consists of the following steps:

1. Define the Node structure: We define a structure called Node to represent a node in the binary tree. Each node contains an integer value and pointers to its left and right child nodes.
2. Create a new node: The createNode function is used to create a new node with the given integer value. It allocates memory for the node and initializes its data and child pointers.
3. Recursive height function: The height function takes a Node pointer as input and recursively calculates the height of the binary tree rooted at that node. It follows these steps:
   • Base case: If the given node is NULL, i.e., the tree is empty, it returns 0.
   • Recursive calls: It recursively calculates the height of the left and right subtrees by calling the height function on the left and right child nodes.
   • Return statement: It returns the maximum height between the left and right subtrees, plus 1 for the current node.
4. Main function:
   • Construct the binary tree: In the main function, we construct a binary tree by creating the nodes and connecting them using the left and right child pointers.
   • Calculate the height: We call the height function with the root of the binary tree to calculate its height.
   • Print the height: Finally, we print the height of the binary tree using printf statement.

The height function uses the concept of recursion to solve the problem. It breaks down the problem of finding the height of a binary tree into subproblems of finding the heights of the left and right subtrees. By solving these subproblems recursively, we can calculate the height of the entire binary tree.

Note: The height of an empty tree (where the root is NULL) is considered 0 in this program.

Input /Output

This output indicates that the height of the binary tree is 3.

The height of a binary tree is the maximum number of edges between the root node and any leaf node. In this example, the maximum number of edges between the root node (1) and any leaf node (4, 5, 6, or 7) is 3, which is the height of the binary tree.

You can modify the program to work with different binary trees by creating the nodes and connections accordingly. The program will then calculate and output the height of the given binary tree.