Problem Statement
Given the root of a binary tree, determine whether it is height-balanced.
A binary tree is balanced if:
For every node,
| Left Height - Right Height | ≤ 1
Brute Force Intuition
In an interview, you can explain it like this:
For every node, calculate the height of its left and right subtrees. If the height difference is more than 1, the tree is not balanced.
The drawback is that the height of the same subtree is computed repeatedly.
Complexity
- Time Complexity: O(N²)
- Space Complexity: O(H)
Brute Force Code
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null)
return true;
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if (Math.abs(leftHeight - rightHeight) > 1)
return false;
return isBalanced(root.left) &&
isBalanced(root.right);
}
private int height(TreeNode root) {
if (root == null)
return 0;
return 1 + Math.max(
height(root.left),
height(root.right));
}
}
Moving Towards the Optimal Approach
Notice that while calculating:
Height
we can also determine whether the subtree is balanced.
Instead of returning only the height,
return:
-1
whenever an unbalanced subtree is found.
This allows us to stop checking further.
Pattern Recognition
Whenever you see:
- Balanced Tree
- Height Difference
- Height of Binary Tree
Think:
Postorder DFS
Key Observation
For every node:
Compute:
Left Height
↓
Right Height
If either subtree is already unbalanced:
Return -1
If:
|Left Height - Right Height| > 1
Again:
Return -1
Otherwise,
return the current height.
Optimal Approach
Step 1
Recursively compute:
Left Height
Step 2
Recursively compute:
Right Height
Step 3
If either returns:
-1
the tree is already unbalanced.
Step 4
If height difference exceeds:
1
return:
-1
Otherwise,
return:
1 + Math.max(leftHeight, rightHeight);
Optimal Java Solution
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
private int height(TreeNode root) {
if (root == null)
return 0;
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if (leftHeight == -1 ||
rightHeight == -1)
return -1;
if (Math.abs(leftHeight -
rightHeight) > 1)
return -1;
return 1 + Math.max(leftHeight,
rightHeight);
}
}
Dry Run
1
/ \
2 3
/
4
Node 4
Left = 0
Right = 0
Height = 1
Node 2
Left = 1
Right = 0
Difference = 1
Balanced
Height = 2
Root 1
Left = 2
Right = 1
Difference = 1
Balanced
Answer:
true
Unbalanced Example
1
/
2
/
3
Node 1:
Left Height = 2
Right Height = 0
Difference = 2
Return -1
Answer:
false
Why Returning -1 Works?
Instead of checking balance separately,
the recursion combines two tasks:
Compute Height
+
Detect Imbalance
The moment an unbalanced subtree is found,
-1 propagates upward,
avoiding unnecessary calculations.
Every node is visited exactly once.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(N) |
| Space Complexity | O(H) |
Where:
-
N= Number of Nodes -
H= Height of the Tree
Interview One-Liner
Use postorder DFS to compute subtree heights, returning
-1whenever an imbalance is detected so the result propagates upward immediately.
Pattern Learned
Postorder DFS
↓
Left Height
↓
Right Height
↓
Check Difference
↓
Return Height
or
-1
Similar Problems
- Balanced Binary Tree
- Diameter of Binary Tree
- Maximum Depth of Binary Tree
- Binary Tree Maximum Path Sum
- Check Height Balanced Tree
Memory Trick
Think:
Go Left
↓
Go Right
↓
Difference > 1 ?
↓
Return -1
↓
Else Return Height
Mental Model
Leaf
↓
Returns Height
↓
Parent
↓
Checks Balance
↓
Returns Height
or
-1
Whenever you hear:
"Balanced Binary Tree"
your brain should immediately think:
Postorder DFS + Return Height or -1
Top comments (0)