#110
Balanced Binary Tree
Easy Height with early exit
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether every node's left and right subtree heights differ by at most 1.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: do the two subtree heights differ by at most 1 at every node?
Why this works: return the height, or -1 as soon as any subtree is unbalanced, so you never recompute.
Example: 1 (2 (3 (4)), -)
node 2: heights 2 vs 0 → -1 → whole tree unbalanced✦Hints open one at a time
Compute heights bottom-up.
Return −1 as a signal that a subtree is already unbalanced.
↗Approach
check(node) returns the height, or −1 if any subtree is unbalanced or this node's children differ by more than 1. The tree is balanced if check(root) != −1.
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public boolean isBalanced(TreeNode root) {
return check(root) != -1;
}
private int check(TreeNode n) {
if (n == null) return 0;
int l = check(n.left);
if (l == -1) return -1;
int r = check(n.right);
if (r == -1 || Math.abs(l - r) > 1) return -1; // unbalanced somewhere
return 1 + Math.max(l, r);
}
}!Common mistake
Checking only the root's two subtrees — every node must be balanced.
Complexity
- Time: O(n).
- Space: O(h).
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon