Balanced Binary Tree

Problem

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

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

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

Constraints:

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

Solution

Approach: DFS with Height Calculation

The key insight is to check if each subtree is balanced while computing its height. We return -1 as a sentinel value to indicate imbalance.

Implementation

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def height(node):
            if not node:
                return 0

            left_height = height(node.left)
            if left_height == -1:
                return -1  # Left subtree is unbalanced

            right_height = height(node.right)
            if right_height == -1:
                return -1  # Right subtree is unbalanced

            # Check if current node is balanced
            if abs(left_height - right_height) > 1:
                return -1  # Current node is unbalanced

            return 1 + max(left_height, right_height)

        return height(root) != -1

Alternative (Separate Checks):

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def height(node):
            if not node:
                return 0
            return 1 + max(height(node.left), height(node.right))

        if not root:
            return True

        left_height = height(root.left)
        right_height = height(root.right)

        if abs(left_height - right_height) > 1:
            return False

        return self.isBalanced(root.left) and self.isBalanced(root.right)

Complexity Analysis

Optimized Approach:

Time Complexity: O(n), where n is the number of nodes. We visit each node once.
Space Complexity: O(h), where h is the height of the tree (recursion stack).

Separate Checks:

Time Complexity: O(n²) in the worst case (unbalanced tree), as we recalculate heights.
Space Complexity: O(h) for recursion stack.

Key Insights

Height-Balanced Definition: At every node, the heights of left and right subtrees differ by at most 1.
Early Termination: Using -1 as a sentinel value allows us to propagate imbalance up the tree immediately, avoiding unnecessary computation.
Bottom-Up Approach: We check balance at each node while computing height in a single pass, more efficient than checking height and balance separately.
All Nodes Must Satisfy: It’s not enough for just the root to be balanced; every node in the tree must satisfy the balance condition.
Post-Order Traversal: We compute heights of children before checking parent’s balance, following post-order pattern.