You are given the root of a binary tree. Your task is to determine whether the tree is height-balanced.
A binary tree is considered height-balanced if, for every node in the tree:
- The height difference between its left and right subtrees is at most 1.
- Both left and right subtrees are also height-balanced.
Here’s the [Problem Link] to begin with.
Example 1
Input: root = [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
Output: true
Example 2
Input: root = [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
Output: false
Explanation: The left subtree has height 3 more than the right subtree, so it is unbalanced.
Intuition and Approach
To check if a tree is balanced:
- Compute the height of left and right subtrees for each node.
- If the absolute difference of heights is greater than 1, the tree is not balanced.
- To make this efficient, use a special return value
-1
to signal imbalance. This allows early termination, avoiding unnecessary work.
We’ll look at two versions:
- Optimal solution – Computes left and right heights, then checks balance.
- Slightly optimal solution – Adds a pruning step by checking left first, and only if it is balanced proceeds to check right.
Optimal Solution
Code Implementation
class Solution:
def solve(self, node):
if node is None:
return 0
leftH = self.solve(node.left)
rightH = self.solve(node.right)
if leftH == -1 or rightH == -1:
return -1
if abs(leftH - rightH) > 1:
return -1
return 1 + max(leftH, rightH)
def isBalanced(self, root: Optional[TreeNode]) -> bool:
height = self.solve(root)
if height == -1:
return False
return True
Code Explanation
- Base case: If the node is
None
, its height is 0. - Recursively compute
leftH
andrightH
. - If either subtree is unbalanced (returns
-1
), propagate-1
upwards. - If the absolute difference of
leftH
andrightH
exceeds 1, return-1
to mark unbalance. - Otherwise, return the actual height
1 + max(leftH, rightH)
. isBalanced(root)
checks the root result. If-1
, returnFalse
, else returnTrue
.
Slightly Optimal Solution
Code Implementation
class Solution:
def solve(self, node):
if node is None:
return 0
leftH = self.solve(node.left)
if leftH == -1:
return -1
rightH = self.solve(node.right)
if rightH == -1:
return -1
if abs(leftH - rightH) > 1:
return -1
return 1 + max(leftH, rightH)
def isBalanced(self, root: Optional[TreeNode]) -> bool:
height = self.solve(root)
if height == -1:
return False
return True
Code Explanation
- This version prunes earlier.
- If the left subtree is already unbalanced (
-1
), it does not bother computing the right subtree. - Similarly, if the right is unbalanced, it exits early.
- This saves unnecessary recursive calls when imbalance is found in large trees.
Time and Space Complexity
- Time Complexity (both versions):
Each node is visited once, and at each node we do constant work.
So time is O(N), whereN
is the number of nodes. - Space Complexity:
The space is due to recursion depth. In the worst case (skewed tree), it can be O(N).
In the best case (balanced tree), it is O(log N).
Conclusion
The Balanced Binary Tree problem is solved by combining height calculation with an early unbalance detection mechanism:
- The optimal solution calculates both left and right subtree heights first.
- The slightly optimal solution improves efficiency by pruning unnecessary checks as soon as imbalance is detected.
Both approaches run in O(N) time and ensure early stopping when imbalance is found, making them efficient in practice.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.