Introduction

A binary tree is considered height-balanced if the difference between the heights of the left and right subtrees of every node is no more than 1. In this guide, we will write a C++ program to check if a binary tree is height-balanced.

The idea is to recursively calculate the height of the left and right subtrees of each node. If the difference in height between the two subtrees is greater than 1 for any node, the tree is not height-balanced.

Program Structure

The program will follow these steps:

1. Define a TreeNode structure to represent nodes in the binary tree.
2. Write a recursive function checkHeight that calculates the height of the tree while checking if the tree is balanced.
3. Write the main function to test the algorithm with a sample binary tree.

Code Implementation

// C++ program to check if a binary tree is height-balanced

#include <iostream>
#include <cmath>  // For the abs() function
using namespace std;

// Define the structure of a tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    // Constructor to initialize the tree node
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Helper function to check the height of the tree and determine if it is balanced
int checkHeight(TreeNode* root) {
    // Base case: if the node is NULL, the height is 0
    if (root == NULL) {
        return 0;
    }

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

    // If either subtree is unbalanced, return -1
    if (leftHeight == -1 || rightHeight == -1) {
        return -1;
    }

    // If the difference in height is more than 1, the tree is unbalanced
    if (abs(leftHeight - rightHeight) > 1) {
        return -1;
    }

    // Return the height of the current node (1 + maximum height of the subtrees)
    return 1 + max(leftHeight, rightHeight);
}

// Function to check if the binary tree is balanced
bool isBalanced(TreeNode* root) {
    // If checkHeight returns -1, the tree is unbalanced; otherwise, it's balanced
    return checkHeight(root) != -1;
}

// Helper function to insert a new node into the binary tree (for testing purposes)
TreeNode* insert(TreeNode* node, int val) {
    if (node == NULL) return new TreeNode(val);  // If the tree is empty, create a new node

    // Otherwise, recursively insert the value into the left or right subtree
    if (val < node->val)
        node->left = insert(node->left, val);
    else
        node->right = insert(node->right, val);

    return node;
}

// Helper function to perform in-order traversal of the binary tree (for testing purposes)
void inOrderTraversal(TreeNode* root) {
    if (!root) return;

    inOrderTraversal(root->left);
    cout << root->val << " ";
    inOrderTraversal(root->right);
}

int main() {
    /* Sample Binary Tree:
              1
            /   \
           2     3
          / \     
         4   5   
    */

    // Creating the binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // Check if the tree is height-balanced
    if (isBalanced(root)) {
        cout << "The tree is height-balanced." << endl;
    } else {
        cout << "The tree is not height-balanced." << endl;
    }

    return 0;
}

Explanation

Let’s break down the program:

1. TreeNode structure: This structure represents a node in the binary tree. Each node stores a value val and pointers to its left and right children.
2. checkHeight function: This recursive function calculates the height of the tree while checking if the tree is balanced:
   • For each node, we calculate the height of its left and right subtrees.
   • If the difference in height between the two subtrees is greater than 1, the function returns -1 to indicate that the tree is unbalanced.
   • If the tree is balanced at the current node, we return the height of the tree rooted at that node (1 + the maximum height of the left and right subtrees).
3. isBalanced function: This function calls the checkHeight function. If checkHeight returns -1, the tree is unbalanced; otherwise, it’s balanced.
4. insert function: This helper function is used to insert nodes into the binary tree for testing purposes.
5. inOrderTraversal function: This function performs an in-order traversal of the binary tree, printing the nodes in sorted order. It is optional for testing purposes.

How the Algorithm Works

The algorithm works by recursively checking the height of the left and right subtrees of each node:

• If the height difference between the left and right subtrees of any node is more than 1, the tree is unbalanced.
• If both subtrees are balanced and the height difference is within 1, we return the height of the tree rooted at the current node.
• If any subtree is unbalanced, the function returns -1 to propagate this information up the recursive calls.

Sample Output

If you run the above program with the provided sample binary tree, the output will be:

The tree is height-balanced.

In this example, the tree is balanced because the height difference between the left and right subtrees of each node is no more than 1.

Conclusion

In this program, we implemented a recursive algorithm to check if a binary tree is height-balanced. The algorithm calculates the height of each subtree and checks whether the difference in height between the left and right subtrees is greater than 1 at any node. If any node violates the height-balance property, the tree is considered unbalanced.

The time complexity of the algorithm is O(N), where N is the number of nodes in the tree. This is because each node is visited once during the recursive calls. The space complexity is O(H), where H is the height of the tree, due to the recursive call stack.