Problem Statement

Given a binary tree, determine if it is height-balanced. 

Given a binary tree, we need to determine whether it is height-balanced or not. A binary tree is considered height-balanced if the heights of the two subtrees of any node never differ by more than one.

Balanced binary trees aim to ensure that the height difference between the left and right subtrees of any node in the tree is minimized. The primary problem is to maintain this balance efficiently, especially during insertion and deletion operations, to prevent the tree from becoming skewed and losing its efficiency.

Examples

Example 1:

Consider the following binary tree:

      A
     / \
    B   C
       / \
      D   E

This tree is balanced because the height difference between the left and right subtrees of any node is at most 1.

Example 2:

    1
   / \
  2   2
 / \
3   3
   / \
  4   4

This binary tree is not height-balanced, as the height difference between the left and right subtrees of the root node 1 is 2.

Theory

A height-balanced binary tree is a tree in which the heights of the left and right subtrees of any node differ by at most one. The height of a node in a binary tree is the number of edges on the longest path from the node to a leaf. Therefore, to determine if a binary tree is height-balanced, we need to calculate the height of each subtree and check if the difference in heights is within the acceptable range.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

The reasoning behind checking if a binary tree is balanced revolves around ensuring that, for every node in the tree, the height difference between the left and right subtrees is no more than one. This condition prevents the tree from being skewed too much to one side, ensuring a balanced structure. By recursively assessing this balance condition at each node, it's possible to determine if the entire tree maintains a balanced state.

Approach:

1. First, check if the root node is null. If it is, return true because an empty tree is inherently balanced.
2. For non-empty trees, recursively calculate the height of both the left and right subtrees using a helper function, often called getHeight. Store these heights and compare them. If the absolute difference between the heights is greater than 1, return false, as this indicates the tree is unbalanced at the current node.
3. If the height difference is 1 or less, proceed by recursively invoking the isBalanced function on the left and right child nodes. If both subtrees are found to be balanced, return true. If either subtree is unbalanced, return false, indicating that the tree overall is not balanced.

Dry Run:

Code:

 #include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isBalanced(TreeNode *root) {
        // If the tree is empty, it's balanced
        if (root == nullptr) {
            return true;
        }

        // Calculate the height of left and right subtrees
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);

        // Check if the absolute difference in heights
        // of left and right subtrees is <= 1
        if (std::abs(leftHeight - rightHeight) <= 1 &&
            isBalanced(root->left) &&
            isBalanced(root->right)) {
            return true;
        }

        // If any condition fails, the tree is unbalanced
        return false;
    }

private:
    // Function to calculate the height of a subtree
    int getHeight(TreeNode *root) {
        // Base case: if the current node is NULL,
        // return 0 (height of an empty tree)
        if (root == nullptr) {
            return 0;
        }

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

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

// Main function
int main() {
    // Creating a sample 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);
    root->left->right->right = new TreeNode(6);
    root->left->right->right->right = new TreeNode(7);

    // Creating an instance of the Solution class
    Solution solution;

    // Checking if the tree is balanced
    if (solution.isBalanced(root)) {
        std::cout << "The tree is balanced." << std::endl;
    } else {
        std::cout << "The tree is not balanced." << std::endl;
    }

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N^2) where N is the number of nodes in the Binary Tree. For each node in the Binary Tree, all other nodes are traversed to calculate its height, resulting in a nested traversal structure, leading to O(N) operations for each of the N nodes, hence O(N * N) = O(N^2).
• Space Complexity: O(1) as no additional data structures or memory is allocated.

2️⃣ Optimal Approach

Intuition:

The O(N*N) time complexity of the previous method can be improved by incorporating the balance check directly within the tree traversal process. Instead of recalculating the heights of the left and right subtrees at each node repeatedly, these heights can be determined in a bottom-up fashion via postorder traversal. This method allows for the efficient validation of balance conditions during traversal, minimizing redundant computations and enabling the early identification of unbalanced nodes.

Algorithm Steps:

1. Perform a postorder traversal of the Binary Tree using recursion: First visit the left subtree, then the right subtree, and finally the root node. During this traversal, compute the heights of the left and right subtrees for each node. Utilize these computed heights to verify the balance condition at the current node.
2. If, at any node, the absolute difference between the heights of the left and right subtrees exceeds 1, or if any subtree is determined to be unbalanced (returns -1), return -1 immediately, signaling that the tree is unbalanced.
3. For a balanced tree, return the height of the current node by taking the greater height of its left or right subtree and adding 1 to account for the current node itself.
4. Continue the traversal process until all nodes have been visited. The final result will either be the height of the entire tree if it is balanced, or -1 if the tree is found to be unbalanced at any point.

Dry Run:

Code:

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Function to check if the tree is balanced
    bool isBalanced(TreeNode *root) {
        // Check if the tree's height difference
        // between subtrees is less than 2
        // If not, return false; otherwise, return true
        return dfsHeight(root) != -1;
    }

private:
    // Recursive function to calculate the height of the tree
    int dfsHeight(TreeNode *root) {
        // Base case: if the current node is NULL,
        // return 0 (height of an empty tree)
        if (root == nullptr) return 0;

        // Recursively calculate the height of the left subtree
        int leftHeight = dfsHeight(root->left);
        // If the left subtree is unbalanced,
        // propagate the unbalance status
        if (leftHeight == -1) return -1;

        // Recursively calculate the height of the right subtree
        int rightHeight = dfsHeight(root->right);
        // If the right subtree is unbalanced,
        // propagate the unbalance status
        if (rightHeight == -1) return -1;

        // Check if the difference in height between left and right subtrees is greater than 1
        // If it's greater, the tree is unbalanced,
        // return -1 to propagate the unbalance status
        if (std::abs(leftHeight - rightHeight) > 1) return -1;

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

// Main function
int main() {
    // Creating a sample 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);
    root->left->right->right = new TreeNode(6);
    root->left->right->right->right = new TreeNode(7);

    // Creating an instance of the Solution class
    Solution solution;

    // Checking if the tree is balanced
    if (solution.isBalanced(root)) {
        std::cout << "The tree is balanced." << std::endl;
    } else {
        std::cout << "The tree is not balanced." << std::endl;
    }

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N) where N is the number of nodes in the Binary Tree.
• Space Complexity: O(1) as no additional data structures or memory is allocated.