This C program checks if a binary tree is height-balanced. A tree is height-balanced if the height differences between the left and right subtrees of any node is no more than one.

Program Explanation

The program is structured into the following components:

• Node Structure: Defines the structure of a binary tree node.
• Utility Function to Calculate Height: Recursively calculates the height of a subtree.
• Is Balanced Function: Determines if the tree is balanced by checking height differences of subtrees for each node.
• Main Function: Demonstrates the functionality by creating a sample tree and checking its balance.

Program Code

// Include necessary headers
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.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 tree
int height(Node* node) {
    if (node == NULL)
        return 0;
    int leftHeight = height(node->left);
    int rightHeight = height(node->right);
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

// Function to check if the binary tree is height-balanced
bool isBalanced(Node* root) {
    if (root == NULL)
        return true;

    int leftHeight = height(root->left);
    int rightHeight = height(root->right);

    if (abs(leftHeight - rightHeight) > 1)
        return false;

    return isBalanced(root->left) && isBalanced(root->right);
}

// Main function to test the program
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->left->left->left = newNode(8); // making the tree imbalanced

    if (isBalanced(root))
        printf("The tree is height-balanced\\n");
    else
        printf("The tree is not height-balanced\\n");

    return 0;
}
    

Key Components of the Program:

• Node Structure: Defines each node in the binary tree.
• newNode Function: Helps to create a new tree node.
• height Function: Computes the height of the tree recursively, required for determining balance.
• isBalanced Function: Recursively checks if the tree is balanced by evaluating the height differences of the left and right subtrees for each node.
• Main Function: Constructs a sample binary tree and checks whether it is balanced.

This structure provides a clear separation of concerns, with each function focusing on a specific task, which aids in maintaining the code effectively. The program checks balance in a straightforward manner, ensuring that all subtrees comply with the balance condition.