Check for balanced binary tree
MediumReturn the height, or a failure sentinel
Problem
Return whether a binary tree is height-balanced (left/right heights differ by at most 1 everywhere).
Check heights bottom-up; if any node's two subtree heights differ by more than 1, it's unbalanced.
The idea
Computing the height at every node separately is O(n²). Instead have the recursion return the height, or -1 to mean 'already unbalanced below', so one postorder pass both measures and validates in O(n).
The trick
- Return -1 as the failure signal and propagate it upwards immediately.
- Balanced means the two subtree heights differ by at most one, at every node.
Step 1 of 8. A node's height is 1 + the taller of its two subtrees. Solve leaves first, then bubble up.
Combine children heights.
1function height(node) {2 if (!node) return 0;3 return 1 + Math.max(height(node.left), height(node.right));4}Input
- nodes
- 6, 5 edges
Output
- max depth
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [3,9,20,null,null,15,7]
- Output:
- true
- Explanation:
- Every node's subtrees differ in height by <=1.
Example 2
- Input:
- tree = [1,2,2,3,3,null,null,4,4]
- Output:
- false
- Explanation:
- One side is too deep → false.
Example 3
- Input:
- tree = []
- Output:
- true
- Explanation:
- Empty tree is balanced.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.