Difficulty: EasyTrees

Balanced Binary Tree

Problem in Plain English

Given the root of a binary tree, decide whether it is height-balanced, meaning the left and right subtrees of every node differ in height by at most one.

Problem Statement

Given the root of a binary tree, determine whether the tree is height-balanced.

A tree is height-balanced when, for every node, the heights of its left and right subtrees differ by no more than 1. An empty tree counts as balanced.

Constraints

The number of nodes is between 0 and 5000, inclusive.
Each node value is between -10000 and 10000, inclusive; values do not affect balance.

Examples

Example 1

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

Leaves 9, 15 and 7 have child heights 0 and 0. Node 20 has child heights 1 and 1; root 3 has child heights 1 and 2. Every gap is at most 1, so the whole tree is balanced.

Example 2

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

The leaves 4 and 4 make their parent 3 height 2. Node 2 on the left has subtree height 3, whereas the right node 2 has height 1. Root 1 has a gap of 2 and fails the rule.

Example 3

Input: root = []
Output: true

There are no nodes that can violate the height rule. The height helper returns 0 for an empty subtree and the verdict is true.

Example 4

Input: root = [1,2,2,3,null,null,3,4,null,null,4]
Output: false

The root has equal subtree heights of 3, but each child 2 has heights 2 and 0. Those internal gaps of 2 make the tree unbalanced despite a passing root comparison.

Example 5

Input: root = [1,2]
Output: true

Root 1 has heights 1 and 0, so a difference of exactly 1 is allowed. The leaf 2 is also balanced.

Intuition

Height counts nodes on the longest downward path, with an empty subtree having height 0. Balance is a local rule that must hold everywhere: in Example 1, node 20 combines heights 1 and 1, then root 3 compares heights 1 and 2. Equal heights at the root alone cannot certify its descendants. A subtree can therefore return either its height or a signal that a lower node has already failed.

Approaches

Top Down Height Check

Solution Details

Reveal Top Down Height Check: intuition, complexity, and code

Intuition

Measure both subtree heights independently at every node, then combine that local test with the verdicts of both children. This direct version deliberately checks all descendants even after a failed test, making the repeated work visible: in Example 1, leaves 15 and 7 are measured for root 3 and then measured again for node 20.

Step-by-Step Logic

For any node, measure each child subtree by recursively taking one plus the larger child height; empty children return 0. At root 3 in Example 1, measuring 9 returns 1, then measuring 15 and 7 lets 20 return 2.
Remember the local gap and recursively check both child subtrees. Root 3 passes its local comparison; node 9 measures two empty children and returns true.
Repeat the same procedure at node 20. Its height calls remeasure leaves 15 and 7 as 1 and 1, then its balance calls visit both leaves, which each compare 0 and 0.
Combine the local comparison with both child verdicts on the way back up. Node 20 returns true and root 3 combines a gap of 1 with two true children, returning true.

Why It Works

Induct on subtree size. An empty tree is balanced and its height is 0. The height helper returns one plus the larger child height, so both measured heights are exact. A nonempty subtree satisfies the definition precisely when its root gap is at most 1 and both child subtrees are balanced. The recursive calls establish those child verdicts, and the final conjunction checks all three necessary and sufficient conditions. Node values and child links are only read.

Dry Run

Top Down Height Check: variable states at each step
Event in execution order	Heights or verdicts returned	Pending check
check(3): height(9) visits its two null children	0, 0 -> height 1	leftHeight = 1
check(3): height(20) measures 15, then 7	each leaf: 0, 0 -> 1; 20: 1, 1 -> 2	rightHeight = 2; gap = 1
check(9): height(null), height(null)	0, 0	gap = 0
check(9): check(null), check(null)	true, true	check(9) returns true
check(20): height(15), height(7) remeasure both leaves	each: 0, 0 -> 1	leftHeight = 1; rightHeight = 1; gap = 0
check(15): both heights and both empty-child checks	0, 0; true, true	check(15) returns true
check(7): both heights and both empty-child checks	0, 0; true, true	check(7) returns true
check(20) combines gap and child verdicts	gap 0; true, true	returns true
check(3) combines gap and child verdicts	gap 1; true, true	returns true

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n)

Let n be the number of nodes and h the height. This version checks every node, even after a failed gap. A chain causes height walks of lengths n-1, n-2, down to 0: their sum is quadratic. A balanced tree takes O(n log n). Auxiliary storage is O(h), worst-case O(n): suspended balance calls and the current height walk share a root-to-leaf path. No nodes or collections are allocated and the returned boolean uses constant space. A depth-5000 chain can exceed runtime stack defaults; verification uses Java -Xss16m, Node --stack_size=16384, and the published Python entry wrapper temporarily reserves recursion limit 12000 and restores it after the call.

Code

Solution.java

1class TreeNode {2    int val;3    TreeNode left, right;4    TreeNode(int val) { this.val = val; }5}6
7class Solution {8    public boolean isBalanced(TreeNode root) {9        if (root == null) return true;10        int leftHeight = height(root.left);11        int rightHeight = height(root.right);12        // Evaluate both children explicitly: this version checks every local rule.13        boolean leftBalanced = isBalanced(root.left);14        boolean rightBalanced = isBalanced(root.right);15        return Math.abs(leftHeight - rightHeight) <= 1 && leftBalanced && rightBalanced;16    }17
18    private int height(TreeNode node) {19        if (node == null) return 0;20        return 1 + Math.max(height(node.left), height(node.right));21    }22}

Hints

Hint 1

Balance is a property of every node, not just the root, so any single-node height check must be repeated or shared.

Hint 2

A height function already visits each subtree, so let it also report imbalance instead of walking the tree twice.

Hint 3

Return -1 for an imbalanced subtree and propagate it upward at once to skip the remaining work.

Edge Cases

An empty tree returns true without any height comparison.
A single node and a two-node chain are balanced; a three-node chain is not.
Equal heights at the root can hide unbalanced descendants, as in Example 4.
Negative values and duplicate values have no effect: only the shape matters.
A deep one-child chain requires a deep recursive descent even for the early-exit approach; the input tree must remain unchanged.

Common Mistakes and Interview Tips

Checking only the root gap and forgetting that every descendant must be balanced too.
Mixing height conventions: these snippets use empty height 0 and leaf height 1. Use the same convention on both sides.
Using a gap of at least 1 as failure: exactly 1 is allowed.
Treating -1 as an ordinary height or overwriting the sentinel before returning it.
Claiming the direct code is linear: it intentionally evaluates both child checks and repeats height walks; the sentinel version removes that repetition.
Assuming recursion is safe at maximum depth. If the runtime stack cannot be configured, discuss an explicit post-order stack; keep any recursion-limit change outside the helper and restore it afterward.

Key Takeaway

When a tree verdict needs subtree data, return the data and the verdict together bottom-up instead of remeasuring top-down.