Problem Statement

Given the root of 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.

Additional information

• The number of nodes in the tree is in the range [0, 5000].
• -10000 <= Node.val <= 10000

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

Example 3:

Input: root = []
Output: true

Brute Force (Top-Down Recursion)

Intuition
The definition of a balanced tree applies to every node. A straightforward way to check this is to write a function that calculates the height of a tree.
Then, for the current node, we check if the height of its left child and the height of its right child differ by no more than 1.
However, checking just the root isn't enough; we must recursively enforce this rule for the left child and the right child as well.

Algorithm

1. Define a helper function height(node) that returns the maximum depth of a node.
2. In the main is_balanced function:

• If root is None, return True (base case).
• Calculate left_height = height(root.left).
• Calculate right_height = height(root.right).
• Check if abs(left_height - right_height) <= 1.
• Recursively check if is_balanced(root.left) is true AND is_balanced(root.right) is true.

3. Return True only if all conditions are met.

def is_balanced(root: Optional[TreeNode]) -> bool:
    # Helper to get height of a node
    def height(node):
        if not node:
            return 0
        return 1 + max(height(node.left), height(node.right))
    
    if not root:
        return True
        
    left_h = height(root.left)
    right_h = height(root.right)
    
    # Check current node AND recursive children
    return (abs(left_h - right_h) <= 1 and 
            is_balanced(root.left) and 
            is_balanced(root.right))

Time & Space Complexity

• Time complexity: O(n²)

• Reason: For every node we visit, we call height(), which traverses the subtree. In the worst case (skewed tree), this results in a quadratic number of operations.

• Space complexity: O(n)

• Reason: Stack space for recursion.

Depth-First Search (Bottom-Up Optimization)

Intuition
The Brute Force approach is inefficient because it recalculates the height of the same nodes repeatedly.
We can optimize this using a Bottom-Up DFS. Instead of just returning the height, our helper function can return a specific "error code" (like -1) if it discovers a subtree is unbalanced.
If a subtree is balanced, it returns its actual height. If it is unbalanced, the -1 bubbles up to the root immediately.

Algorithm

1. Define a helper function dfs(node):

• If node is None, return 0.
• Recursively call left = dfs(node.left) and right = dfs(node.right).
• If left is -1 OR right is -1, it means a child is already unbalanced. Return -1.
• If abs(left - right) > 1, the current node is unbalanced. Return -1.
• Otherwise, return 1 + max(left, right) (the height).

2. In the main function, call dfs(root).
3. If the result is -1, return False. Otherwise, return True.

def is_balanced(root: Optional[TreeNode]) -> bool:
    
    def dfs(node):
        if not node:
            return 0
        
        left_height = dfs(node.left)
        if left_height == -1:
            return -1
            
        right_height = dfs(node.right)
        if right_height == -1:
            return -1
            
        if abs(left_height - right_height) > 1:
            return -1
            
        return 1 + max(left_height, right_height)
        
    return dfs(root) != -1

Time & Space Complexity

• Time complexity: O(n)

• Reason: We traverse every node exactly once in a bottom-up fashion.

• Space complexity: O(h)

• Reason: The recursion stack depends on the height of the tree.