5.8 Balanced Binary Tree

5.8.1 Problem Metadata

5.8.2 Description

Given 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 depth of the two subtrees of every node never differ by more than 1.

5.8.3 Examples

Example 1:
Balanced tree example

Figure 5.2: Balanced tree example 

Input: root = [3,9,20,null,null,15,7]
Output: true
Explanation: Height of left subtree = 1, height of right subtree = 2, difference = 1 (balanced)
Example 2:
Unbalanced tree example

Figure 5.3: Unbalanced tree example 

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Explanation: Left subtree has much greater depth than right subtree

Example 3:

Input: root = []
Output: true

5.8.4 Constraints

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

5.8.5 Solution - Recursive DFS

5.8.5.1 Walkthrough

Use a recursive depth-first search to compute the height of each subtree.

For each node: 1. Recursively compute the height of the left subtree 2. Recursively compute the height of the right subtree 3. Check if the absolute difference between heights is greater than 1 4. If unbalanced at any node, propagate -1 upward to indicate imbalance 5. Otherwise, return the maximum height + 1

The key insight is to combine height calculation with balance checking in a single pass.

5.8.5.2 Analysis

  • Time Complexity: O(n) - Each node is visited exactly once
  • Space Complexity: O(h) - Recursion call stack depth equals tree height h, where h can be log(n) for balanced trees or n for skewed trees

5.8.5.3 Implementation Steps

  1. If root is null, return 0 (base case)
  2. Recursively get height of left subtree: lHeight = getHeight(root.left)
  3. Recursively get height of right subtree: rHeight = getHeight(root.right)
  4. If either subtree returned -1 (unbalanced), propagate -1 upward
  5. If |lHeight - rHeight| > 1, return -1 (unbalanced)
  6. Otherwise, return max(lHeight, rHeight) + 1

5.8.5.4 Code - Java

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

private int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int lHeight = getHeight(root.left);
    int rHeight = getHeight(root.right);

    // If left or right subtree is unbalanced, propagate -1
    if (lHeight == -1 || rHeight == -1) {
        return -1;
    }

    // If current node is unbalanced, return -1
    if (Math.abs(lHeight - rHeight) > 1) {
        return -1;
    }

    // Return height of current subtree
    return Math.max(lHeight, rHeight) + 1;
}

5.8.5.5 Code - Golang

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }

    return dfs(root) != -1
}

func dfs(node *TreeNode) int {
    if node == nil {
        return 0
    }

    lHeight := dfs(node.Left)
    rHeight := dfs(node.Right)

    // If left or right subtree is unbalanced, return -1
    if lHeight == -1 || rHeight == -1 {
        return -1
    }

    // If current node is unbalanced, return -1
    if math.Abs(float64(lHeight - rHeight)) > 1 {
        return -1
    }

    // return height of current subtree
    return max(lHeight, rHeight) + 1
}