Day 11 - Balanced Binary Tree

🌲 Problem:

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

A binary tree is height-balanced if:

🧪 Examples:

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

📏 Constraints:

• The number of nodes is in the range [0, 10^5]

• Node values: -10^4 <= val <= 10^4

🧠 How to Approach It

This is a recursive post-order traversal problem.

At each node:

1. Recursively check left and right subtrees

2. Track their heights

3. Confirm their height difference is no more than 1

4. Return:

   • whether the current subtree is balanced

   • the height of the current subtree

This avoids re-computation and ensures we check bottom-up — which is key for balanced tree checks.

✅ Python Solution:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        
        def dfs(node):
            if not node:
                return [True, 0]
            
            left_balanced, left_height = dfs(node.left)
            right_balanced, right_height = dfs(node.right)
            
            is_bal = (
                left_balanced and 
                right_balanced and 
                abs(left_height - right_height) <= 1
            )
            
            return [is_bal, 1 + max(left_height, right_height)]
        
        return dfs(root)[0]

⏱ Time & Space Complexity:

• Time: O(n) — each node is visited once

• Space: O(h) for recursion stack (worst case O(n) in a skewed tree)

💬 TL;DR:

• Go bottom-up with DFS

• Check subtree heights at each node

• Bubble up the result: is balanced + current height