49.Balanced Binary Tree

EasyTrees · 4/15

Problem

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

Checking only the root is not enough — the condition must hold at each node.

Examples

Input:  root = [3,9,20,null,null,15,7]
Output: true
Explanation: At the root, heights are 1 (left) and 2 (right); every other node also differs by at most 1.

Input:  root = [1,2,2,3,3,null,null,4,4]
Output: false
Explanation: At the root, the left subtree has height 3 and the right subtree has height 1.

Input:  root = []
Output: true

Constraints

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

💡 Key Insight

Being balanced is a local check (|hL - hR| <= 1) applied everywhere, and it needs subtree heights. A post-order DFS computes the height of each subtree from its children's heights, so it can check the balance condition at the same time — and signal failure with a sentinel like -1 so the whole thing runs in one O(n) pass instead of recomputing heights at every node.

Brute Force (Top-Down)

TimeO(n²) as the usual upper boundSpaceO(h)

Intuition

Directly translate the definition: a tree is balanced if the root's two subtree heights differ by at most one and both subtrees are themselves balanced. Heights come from a separate helper that is called again and again.

Algorithm

If root is null, return true.
If |height(root.left) - height(root.right)| > 1, return false.
Return isBalanced(root.left) && isBalanced(root.right).

Visualization

Tree [1,2,2,3,3,null,null,4,4]:
            1
           / \
          2   2
         / \
        3   3
       / \
      4   4

root: height(left) = 3, height(right) = 1 -> |3 - 1| = 2 > 1 -> false

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(height(root.left) - height(root.right)) > 1) {
            return false;
        }
        // both subtrees must be balanced too
        return isBalanced(root.left) && isBalanced(root.right);
    }

    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }
}

Complexity

Time: O(n²) as the usual upper bound — height(node) costs O(size of subtree) and is recomputed for every node that is checked; for a perfectly balanced tree this sums to O(n log n).
Space: O(h) — recursion depth.

Bottom-Up DFS with SentinelOptimal

TimeO(n)SpaceO(h)

Intuition

Compute heights bottom-up and check balance while returning. If any subtree is unbalanced, return -1 instead of a height; every ancestor sees the -1 and passes it straight up. So one post-order pass both measures heights and detects imbalance, and it stops doing real work as soon as a violation is found.

Algorithm

check(node) returns the height of node's subtree, or -1 if it is unbalanced.
- If node is null, return 0.
- left = check(node.left); if left == -1, return -1.
- right = check(node.right); if right == -1, return -1.
- If |left - right| > 1, return -1.
- Return 1 + max(left, right).
The tree is balanced iff check(root) != -1.

Dry Run

flowchart TD
    N1["1<br/>L=3, R=1<br/>diff 2 -> returns -1"] --> N2a["2<br/>L=2, R=1<br/>returns 3"]
    N1 --> N2b["2<br/>returns 1"]
    N2a --> N3a["3<br/>L=1, R=1<br/>returns 2"]
    N2a --> N3b["3<br/>returns 1"]
    N3a --> N4a["4<br/>returns 1"]
    N3a --> N4b["4<br/>returns 1"]

Every subtree below the root is balanced, but at the root |3 - 1| = 2, so check returns -1 and the answer is false.

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return check(root) != -1;
    }

    // height of the subtree, or -1 if it is not balanced
    private int check(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = check(node.left);
        if (left == -1) return -1;   // propagate failure early
        int right = check(node.right);
        if (right == -1) return -1;
        if (Math.abs(left - right) > 1) {
            return -1;
        }
        return 1 + Math.max(left, right);
    }
}

Complexity

Time: O(n) — each node is visited at most once.
Space: O(h) — recursion depth; O(n) for a skewed tree.

Complexity Comparison

Approach	Time	Space
Brute Force (Top-Down)	O(n²)	O(h)
Bottom-Up DFS with Sentinel	O(n)	O(h)

Common Pitfalls

Only comparing the heights at the root. A tree like [1,2,2,3,null,null,3,4,null,null,4] has equal root-level heights but is unbalanced deeper down.
Confusing "balanced" with "complete" or "perfect" — a balanced tree may have gaps, as long as sibling heights differ by at most 1.
Forgetting to propagate the -1 sentinel: if you compute Math.abs(-1 - 2) you may accidentally treat failure as a valid height.
An empty tree is balanced — return true, not false.