C Program: Calculate height of Binary Tree with graceful handling

Last update on December 20 2024 13:09:36 (UTC/GMT +8 hours)

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.