This C program calculates the height of a binary tree, defined as the number of edges in the longest path from the root node to the farthest leaf node.

Program Explanation

The program is structured as follows:

• Node Structure: Defines the structure of a binary tree node.
• Function to Create a New Node: Allocates a new node with given data.
• Function to Calculate Height: Recursively calculates the height of the binary tree.
• Main Function: Creates a sample binary tree and calculates its height.

Program Code

// Include necessary headers
#include <stdio.h>
#include <stdlib.h>

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

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

// Function to calculate the height of the binary tree
int height(Node* root) {
    if (root == NULL)
        return 0; // The height of an empty tree is 0
    else {
        // Compute the height of each subtree
        int leftHeight = height(root->left);
        int rightHeight = height(root->right);
        // Return the larger one
        return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
    }
}

// Main function to demonstrate the tree height calculation
int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->right = newNode(6);

    printf("Height of the tree is %d\\n", height(root));
    return 0;
}
    

Key Components of the Program:

• Node Structure: Defines each node in the binary tree containing data and pointers to left and right children.
• newNode Function: Helps to allocate and initialize a new node with specified data.
• height Function: Recursively calculates the height of the tree. It compares the heights of the left and right subtrees and returns the greater of the two, plus one to account for the current node.
• Main Function: Constructs a sample binary tree, calculates its height using the height function, and prints the result.

This program structure offers a clear and organized approach to managing binary tree operations, with a focus on determining the maximum depth or height of the tree effectively.