Balanced Binary Tree

Easy Trees & BST Postorder + Multiple Return Values Original on LeetCode

Balanced Binary Tree is a easy trees & bst problem solved with the postorder + multiple return values pattern. The best approach, optimal (postorder returning height or -1), runs in O(n) time and O(h) space. Below are 2 approaches in Java, from top-down (height at every node) up.

Problem

Decide whether a binary tree is height-balanced: for every node, the heights of its left and right subtrees differ by at most one.

Examples

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

Constraints

The tree has 0 to 5000 nodes.
Balanced: at every node, the subtree heights differ by at most 1.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Top-down (height at every node)	`O(n²)`	`O(h)`
Optimal (postorder returning height or -1)	`O(n)`	`O(h)`

1Top-down (height at every node)

TimeO(n²)On a skewed tree, height is recomputed for every node.

SpaceO(h)

For each node compute both subtree heights with a separate function and check the difference, then recurse. Heights are recomputed many times.

balanced(n) = |h(left) - h(right)| <= 1 && balanced(left) && balanced(right).

Java

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(height(root.left) - height(root.right)) <= 1
                && isBalanced(root.left) && isBalanced(root.right);
    }

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

2Optimal (postorder returning height or -1)

TimeO(n)

SpaceO(h)

One postorder pass returns two things in one int: the height, or -1 if the subtree is unbalanced. Children are checked before the parent, so each node is visited once.

h(null) = 0.
l = h(left), r = h(right); if either is -1 or |l - r| > 1, return -1.
return 1 + max(l, r).

Java

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    private int height(TreeNode n) {
        if (n == null) return 0;
        int l = height(n.left);
        if (l == -1) return -1;
        int r = height(n.right);
        if (r == -1 || Math.abs(l - r) > 1) return -1;
        return 1 + Math.max(l, r);
    }
}

Edge cases to test

Empty tree (balanced)
Root is balanced but a deeper node is not

Hints

Hint 1

Return the height from the recursion, and use -1 to mean 'already unbalanced' so the check stops early.

FAQ

What is the best time complexity for Balanced Binary Tree?

Optimal (postorder returning height or -1) runs in O(n) time and O(h) extra space.

Which pattern does Balanced Binary Tree use?

It is a trees & bst problem that uses the postorder + multiple return values pattern. Other problems with the same pattern: Validate Binary Search Tree, Children Sum in a Binary Tree, Largest BST.

Is there a brute force solution for Balanced Binary Tree?

Yes. Top-down (height at every node) takes O(n²) time and O(h) space. For each node compute both subtree heights with a separate function and check the difference, then recurse.

Which edge cases should I test for Balanced Binary Tree?

Empty tree (balanced); Root is balanced but a deeper node is not.