#110 Balanced Binary Tree

frequently reported atBloomberg Amazon Microsoft Meta Google

the problem

In plain words

A tree is height-balanced if, at every node, the heights of the left and right subtrees differ by at most 1. Return whether the tree is balanced.

in root = [3,9,20,null,null,15,7]

out true

in root = [1,2,2,3,3,null,null,4,4]

out false

in root = []

out true

0 ≤ number of nodes ≤ 5000
-10⁴ ≤ Node.val ≤ 10⁴

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTree DFS (bottom-up)

Checking only the root is not enough — every node must pass. Compute heights bottom-up and use −1 to say "already unbalanced" so the bad news travels up instantly.

solutions

From brute force to optimal

At each node compare height(left) and height(right), then recurse into both children.

If |h(left) − h(right)| > 1 → false.
Else return balanced(left) && balanced(right).

timeO(n log n) balanced, O(n²) bound

Each node's height is recomputed once per ancestor; on a balanced tree that's log n ancestors.

spaceO(h)

Recursion stack.

javajava.util.*

1class Solution {2    public boolean isBalanced(TreeNode root) {3        if (root == null) return true;4        if (Math.abs(height(root.left) - height(root.right)) > 1) return false;5        return isBalanced(root.left) && isBalanced(root.right);   // heights get recomputed below6    }7 8    private int height(TreeNode node) {9        if (node == null) return 0;10        return 1 + Math.max(height(node.left), height(node.right));11    }12}

check(node) returns the height, or −1 if anything inside is unbalanced.

check(null) = 0.
If either child returns −1 → return −1.
If |left − right| > 1 → return −1.
Else return 1 + max.

timeO(n)

Each node is checked once; we stop early on the first imbalance.

spaceO(h)

Recursion stack.

javajava.util.*

1class Solution {2    private static final int UNBALANCED = -1;3 4    public boolean isBalanced(TreeNode root) {5        return check(root) != UNBALANCED;6    }7 8    /** Height of the subtree, or -1 as soon as any part of it is unbalanced. */9    private int check(TreeNode node) {10        if (node == null) return 0;11        int left = check(node.left);12        if (left == UNBALANCED) return UNBALANCED;          // stop early, pass the bad news up13        int right = check(node.right);14        if (right == UNBALANCED) return UNBALANCED;15        if (Math.abs(left - right) > 1) return UNBALANCED;16        return 1 + Math.max(left, right);17    }18}

in the room

How to say it in the interview

talk track

Show the top-down version's cost first (heights recomputed), then fix it by returning height and balance in one pass.
Explain the −1 sentinel — or use a record if you want it self-documenting.

traps

Only comparing the root's two heights: [1,2,3,4,null,5,null,6] passes at the root but node 2 is unbalanced.

what they ask next

Follow-ups

Why do self-balancing BSTs care about this?

AVL trees keep exactly this property after every insert/delete, guaranteeing height ≤ ~1.44 log₂ n, so search stays O(log n).

before you submit

Edge cases to test

Empty tree → true.
The root passes but a node below fails: [1,2,3,4,null,5,null,6] → false.
The sparsest legal trees (every node off by exactly 1) must still return true.

practise next