🌟 Elegant Python3 Solution | Detailed Explanation | Beats 100% Submissions 🚀
IntuitionThe problem asks us to determine whether a binary tree is balanced. A balanced binary tree is defined as one in which the height difference between the
[![image.png](https://assets.leetcode.com/users/images/e4f5c116-7608-46f0-b65d-1072112564fc_1735231815.5009854.png)](https://leetcode.com/problems/balanced-binary-tree/submissions/1489044483/)
# Intuition
The problem asks us to determine whether a binary tree is balanced. A balanced binary tree is defined as one in which the height difference between the left and right subtrees of any node is at most 1. Additionally, both the left and right subtrees must also be balanced. This suggests a recursive approach where we check the balance condition at each node while simultaneously calculating its height.

The most efficient way to solve this problem is to use a **bottom-up recursive traversal**:
1. Start from the leaf nodes and compute the height of each subtree.
2. Check if the height difference is valid as we propagate the height information back up the recursion stack.
3. If any subtree is unbalanced, propagate a failure signal (-1) up the stack, terminating further checks.

---

# Approach
1. **Recursive Height Calculation**:
   - Define a helper function, `height`, that computes the height of a subtree rooted at the current node.
   - If the subtree is balanced, return the height of the subtree.
   - If the subtree is not balanced, return a special value (-1) to indicate failure.

2. **Base Case**:
   - If the current node is `None` (empty subtree), return a height of `0`. An empty subtree is inherently balanced.

3. **Recursive Step**:
   - Compute the height of the left subtree (`lh`) and the right subtree (`rh`) by recursively calling the `height` function.
   - If either subtree is unbalanced (i.e., `lh == -1` or `rh == -1`), propagate the unbalanced signal upward by returning `-1`.
   - Check the balance condition: If the height difference between the left and right subtrees exceeds 1, return `-1` to indicate imbalance.

4. **Combine Results**:
   - If the subtree is balanced, compute its height as `max(lh, rh) + 1` and return it.

5. **Final Check**:
   - Use the result of the `height` function in the main function `isBalanced`.
   - If the height is non-negative, the tree is balanced. Otherwise, it is not.

---

# Complexity

- **Time Complexity**:  
  $$O(n)$$  
  Each node is visited exactly once. The height of each subtree is calculated in constant time per node during the recursive traversal.

- **Space Complexity**:  
  $$O(h)$$  
  The recursion stack requires space proportional to the height of the tree. For a balanced tree, the height is $$O(\log n)$$. For a completely unbalanced tree, the height is $$O(n)$$.

---

# Code
```python3
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        return (self.height(root) >= 0)
    
    def height(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0  # Base case: an empty subtree has height 0
        
        # Recursive calls to calculate heights of left and right subtrees
        lh, rh = self.height(root.left), self.height(root.right)
        
        # If either subtree is unbalanced or the current node is unbalanced, return -1
        if lh < 0 or rh < 0 or abs(lh - rh) > 1:
            return -1
        
        # If balanced, return the height of the subtree
        return max(lh, rh) + 1
```
![image.png](https://assets.leetcode.com/users/images/8a750918-382f-4b3b-87a1-bb7e40f6d420_1735232076.9336126.png)

['Python3']