What does height-balanced mean?

For every node, the heights of its left and right subtrees differ by at most 1. Checking only the root is not enough: a deeper node can be unbalanced while the root's two sides have equal height.

Why return -1 instead of computing heights separately?

Calling a separate height function at every node recomputes the same subtrees again and again, which is O(n²) on a skewed tree. Returning the height and using -1 to mean unbalanced gets both answers from one call per node: O(n).

Why stop when the left side returns -1?

Once any subtree is unbalanced, the whole tree is. There is no point visiting the right subtree; returning -1 straight away saves the work.

Balanced Binary Tree

Check whether every node's two subtrees differ in height by at most one, in one bottom-up DFS that returns -1 for unbalanced.

EasySolve on LeetCode

Problem Understanding

Balanced Binary Tree: return true if the tree is height-balanced, meaning that for every node, its left and right subtree heights differ by at most 1.

Examples: [3, 9, 20, null, null, 15, 7] is balanced. [1, 2, 2, 3, 3, null, null, 4, 4] is not: the root's left subtree has height 3 and its right has height 1.

Attempt 1: Height at Every Node

For each node, compute the height of both subtrees with a separate function and compare. It is correct, but the height of a deep subtree is recomputed for every ancestor: O(n log n) on a balanced tree and O(n²) on a skewed one.

The Intuition: One Number Carries Both Answers

A bottom-up DFS already computes every subtree's height once. Let it return one extra signal: -1 means "unbalanced somewhere below".

An empty node has height 0.
Get the left height; if it is -1, return -1 at once.
Get the right height; if it is -1, or the two differ by more than 1, return -1.
Otherwise return max(left, right) + 1.

The tree is balanced exactly when the root does not return -1.

Interactive Walkthrough

Calls in progress are outlined, and each node's returned height appears under it when it returns. A node whose two sides are more than 1 apart turns red with -1, and every ancestor above it passes the -1 straight up.

Dry Run Table

Input: [1, 2, 2, 3, 3, null, null, 4, 4]

Node	left	right	Returns
4, 4 (leaves)	0	0	1
3 (with 4, 4)	1	1	2
3 (leaf)	0	0	1
2 (left)	2	1	3
2 (right)	0	0	1
1 (root)	3	1	-1 (differ by 2)

The root returns -1, so the answer is false.

The Solution Template

Bottom-up DFS returning the height, or -1 for unbalanced.

Balanced Binary Tree Code

1var isBalanced = function(root) {
2    const height = (node) => {
3        if (!node) return 0;
4        const left = height(node.left);
5        if (left === -1) return -1;
6        const right = height(node.right);
7        if (right === -1 || Math.abs(left - right) > 1) return -1;
8        return Math.max(left, right) + 1;
9    };
10    return height(root) !== -1;
11};

Edge Cases & Common Mistakes

Empty tree: balanced; height(null) is 0, not -1.
Only checking the root: a tree can be equal in height at the root and still be unbalanced deeper down.
Comparing node counts instead of heights: balance is about heights.
Recomputing heights at every node: correct but O(n²) on a chain; return the height and the verdict together.

Summary

Return each subtree's height from a bottom-up DFS, and use -1 to mean "unbalanced below". A node returns -1 if either side did or if its two heights differ by more than 1. One call per node: O(n).

More practice: DSA interview questions with answers · patterns cheat sheet

Same Tree

Subtree of Another Tree