Balanced Binary Tree
Check whether every node has left and right subtree heights differing by at most one.
Key concepts at a glance — for those who already know the basics.
Problem Statement
Balanced Binary Tree
Given the root of a binary tree, return true if it is height-balanced, otherwise return false.
Balance Rule: for every node, |height(left) - height(right)| <= 1
Intuition
Bottom-up DFS
Use post-order recursion so each node receives left and right heights from children.
Sentinel -1
Return -1 when unbalanced. Parents immediately propagate -1 without extra work.
One Pass
Compute heights and validate balance together in O(n).
Diagram
Balanced - true
Not balanced - false
Dry Run
| Call | Left | Right | |diff| | Return |
|---|---|---|---|---|
| check(9) | 0 | 0 | 0 | 1 |
| check(15) | 0 | 0 | 0 | 1 |
| check(7) | 0 | 0 | 0 | 1 |
| check(20) | 1 | 1 | 0 | 2 |
| check(3) | 1 | 2 | 1 | 3 (balanced) |
Complexity
Time Complexity
O(n)
Every node is visited once in the recursive pass.
Space Complexity
O(h)
Recursion stack height. O(log n) balanced, O(n) skewed.
Interview tip: Mention naive O(n^2) top-down first, then immediately improve to one-pass bottom-up DFS with sentinel -1.
Ready to see it in action?
Step through the visualizer to watch the algorithm state update live.