C Program: Calculate height of Binary Tree with graceful handling

C Program to implement Tree Structure: Exercise-4 with Solution

Write a C program to calculate the height of a binary tree. Ensure the program handles empty trees gracefully.

Sample Solution:

C Code:

// Including necessary header files
#include <stdio.h>
#include <stdlib.h>

// Structure for a binary tree node
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

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

// Function to insert a node into the binary tree
struct TreeNode* insertNode(struct TreeNode* root, int value) {
    if (root == NULL) {
        return createNode(value);
    }

    if (value < root->data) {
        root->left = insertNode(root->left, value);
    } else if (value > root->data) {
        root->right = insertNode(root->right, value);
    }

    return root;
}

// Function to calculate the height of a binary tree
int treeHeight(struct TreeNode* root) {
    if (root == NULL) {
        return 0; // Height of an empty tree is 0
    }

    // Recursively calculate the height of the left and right subtrees
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);

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

// Function to free the memory allocated for the binary tree
void freeTree(struct TreeNode* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

int main() {
    struct TreeNode* root = NULL;
    int nodeValue;
    char choice;

    // Insert nodes into the binary tree
    do {
        printf("Input a value to insert into the binary tree (enter 0 to stop): ");
        scanf("%d", &nodeValue);

        if (nodeValue != 0) {
            root = insertNode(root, nodeValue);
        }

    } while (nodeValue != 0);

    // Calculate and display the height of the binary tree
    int height = treeHeight(root);
    printf("\nHeight of the Binary Tree: %d\n", height);

    // Free allocated memory
    freeTree(root);

    return 0;
}

Output:

Input a value to insert into the binary tree (enter 0 to stop): 45
Input a value to insert into the binary tree (enter 0 to stop): 18
Input a value to insert into the binary tree (enter 0 to stop): 12
Input a value to insert into the binary tree (enter 0 to stop): 8
Input a value to insert into the binary tree (enter 0 to stop): 4
Input a value to insert into the binary tree (enter 0 to stop): 0

Height of the Binary Tree: 5

Explanation:

In the exercise above,

• Structure Definition (struct TreeNode):
• Defines a structure for a binary tree node (TreeNode) with integer data, and pointers to the left and right children.
• Node Creation Function (createNode):
• Allocates memory for a new node and initializes its data and pointers.
• Node Insertion Function (insertNode):
• Inserts a new node into the binary tree while maintaining the binary search tree property.
• Tree Height Calculation Function (treeHeight):
• Recursively calculates and returns the height of the binary tree.
• Memory Deallocation Function (freeTree):
• Frees the memory allocated for the binary tree nodes.
• Main Function (main):
• Initializes the root of the binary tree to NULL.
• Allows the user to input values to insert into the binary tree until the user enters 0.
• Calls the treeHeight function to calculate and display the height of the binary tree.
• Frees the memory allocated for the binary tree.

Flowchart:

C Programming Code Editor:

Previous: C Program: Binary search Tree insertion with sorted in-order traversal.
Next: C Program: Binary Tree deletion with BST maintenance.