Balanced Binary Tree easy

Problem Statement

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

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1

Input: root = [3,9,20,null,null,15,7] Output: true

Example 2

Input: root = [1,2,2,3,3,null,null,4,4] Output: false

Steps

1. Recursive Depth Calculation: We'll use a recursive helper function getHeight to calculate the height of each subtree. The height of an empty tree is -1, and the height of a non-empty tree is 1 + max(height of left subtree, height of right subtree).

2. Height Difference Check: Within the getHeight function, we'll check the absolute difference between the heights of the left and right subtrees. If this difference is greater than 1, we immediately know the tree is not balanced, so we return INT_MIN to signal this. Using INT_MIN ensures that this unbalanced state propagates up the recursion.

3. Balanced Check: The main isBalanced function calls getHeight on the root node. If the returned height is not INT_MIN, the tree is balanced; otherwise, it's not.

Explanation

The solution employs a post-order traversal approach. We first recursively compute the height of the left and right subtrees. If either subtree is unbalanced (height difference > 1), we immediately return INT_MIN to halt further computation and signal unbalance. Otherwise, we compute the height of the current node and return it. This efficient approach avoids redundant computations by stopping the recursion early if an imbalance is detected.

Code

#include <iostream>
#include <algorithm>
#include <limits> // for INT_MIN

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int getHeight(TreeNode* root) {
        if (root == nullptr) return -1;

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

        if (leftHeight == INT_MIN || rightHeight == INT_MIN || abs(leftHeight - rightHeight) > 1) {
            return INT_MIN; 
        }

        return 1 + max(leftHeight, rightHeight);
    }

    bool isBalanced(TreeNode* root) {
        return getHeight(root) != INT_MIN;
    }
};

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. In the worst case, we visit each node once.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be N, resulting in O(N) space complexity. In a balanced tree, H is log₂(N), resulting in O(log N) space complexity.