Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. A binary tree is height-balanced if for every node, the heights of its left and right subtrees differ by at most one.

Example 1

Input: root = [3,9,20,null,null,15,7] Output: true Explanation: Heights: left subtree = 1, right subtree = 2. |1-2| = 1 ≤ 1. All subtrees similarly satisfy the condition.

Example 2

Input: root = [1,2,2,3,3,null,null,4,4] Output: false Explanation: The left subtree of root has height 3 while the right has height 1. |3-1| = 2 > 1.

Constraints:

0 <= Number of nodes <= 5000
-10⁴ <= Node.val <= 10⁴

Solution: Bottom-Up DFS (O(n))
Complexity Analysis

Solution: Bottom-Up DFS (Single Pass)

A naive top-down approach computes height repeatedly for the same subtrees: O(n log n) for balanced, O(n²) for skewed. The optimal approach is a single bottom-up DFS pass that simultaneously computes height and checks balance, using the sentinel value -1 to propagate imbalance up the call stack.

Algorithm:

If the node is null, return height 0.
Recursively get the height of the left subtree; if it returns -1, propagate -1 upward.
Recursively get the height of the right subtree; if it returns -1, propagate -1 upward.
If |leftHeight - rightHeight| > 1, return -1 (imbalanced signal).
Otherwise return 1 + Math.max(leftHeight, rightHeight).

Java

public boolean isBalanced(TreeNode root) {
    return checkHeight(root) != -1;
}

// Returns height if subtree is balanced, -1 if imbalanced
private int checkHeight(TreeNode node) {
    if (node == null) return 0;

    int leftHeight = checkHeight(node.left);
    if (leftHeight == -1) return -1; // propagate imbalance

    int rightHeight = checkHeight(node.right);
    if (rightHeight == -1) return -1; // propagate imbalance

    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1; // current node is imbalanced
    }

    return 1 + Math.max(leftHeight, rightHeight);
}

Note: This single-pass approach is O(n) because each node is visited exactly once. The -1 sentinel short-circuits processing of subtrees once an imbalance is detected.

Complexity Analysis

Time: O(n). Each node is visited exactly once in the bottom-up DFS.
Space: O(h). Recursion stack depth equals the tree height h (O(log n) balanced, O(n) skewed).