110. Balanced Binary Tree

Time: O(n)

Space: O(h)

Intuition

A tree is balanced iff for every node, |height(left) - height(right)| <= 1. Compute height bottom-up; return -1 as a sentinel when imbalance is detected to short-circuit the recursion.

Algorithm

1Height(node): if null, return 0.
2lh = Height(left). If lh == -1, return -1.
3rh = Height(right). If rh == -1, return -1.
4If |lh - rh| > 1, return -1.
5Return max(lh, rh) + 1.
6IsBalanced: return Height(root) != -1.

Example Walkthrough

Input: root = [3,9,20,null,null,15,7]

1.Height(9)=1, Height(20): Height(15)=1, Height(7)=1 -> max+1=2.
2.Height(3): lh=1, rh=2. |1-2|=1 <= 1 . Return 3.

Output: true

Common Pitfalls

•Do not compute height separately for balance check and height - that creates O(n^2). Combine into one bottom-up pass.

110.cs

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
// Approach: DFS returning subtree height. Return –1 to signal imbalance
// and propagate it upward immediately.
// Time: O(n) Space: O(h)

public class Solution
{
    public bool IsBalanced(TreeNode root)
    {
        if (root == null)
            return true;

        return height(root) != -1;
    }

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

        int lh = height(root.left);
        int rh = height(root.right);

        if (Math.Abs(lh - rh) > 1 || lh == -1 || rh == -1)
            return -1;

        return Math.Max(lh, rh) + 1;
    }
}

Was this solution helpful?