LeetCode #110: Balanced Binary Tree

Problem Overview

The problem is to determine if a given binary tree is height-balanced. A binary tree is considered balanced if, for every node, the height difference between its left and right subtrees is no more than 1.

---

Constraints & Edge Cases

• The input is the root of a binary tree.
• A null (empty) tree is considered balanced.
• Must check the balance condition at every node.
• Avoid repeated calculations of subtree height to stay efficient.

---

Approach & Thought Process

1. Initial idea: My first instinct was to write a function that checks the height of each subtree and compares it at every node. But this led to repeated recalculations of heights, resulting in O(n²) time complexity in the worst case.

2. Final approach: I rewrote it using a bottom-up recursive strategy. At each node, I return both:

   • Whether the subtree rooted at that node is balanced
   • The height of the subtree

   This way, each subtree’s height is computed only once, and the recursion can terminate early if an unbalanced subtree is found. The final time complexity is O(n).

---

Code

class Solution {
public:


    int height(TreeNode *root)
    {
        if(!root)
            return 0;
        
        int l = 0;
        int r = 0;
        l = 1 + height(root->left);
        if(l == -1) return -1;
        r = 1 + height(root->right);
        if(r == -1) return -1;

        if(abs(l-r) > 1) return -1;

        return max(l,r);
    }
    bool isBalanced(TreeNode* root) {
        int ans = height(root);
        return ans==-1 ? false : true;
    }
};