Problem Statement:
Given a binary tree, determine if it is height-balanced.
Examples:
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Example 3:
Input: root = []
Output: true
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -104 <= Node.val <= 104
Approach
- Use
post-order traversalto compute the height of left and right subtrees. - At each node, check if the height difference is more than 1.
- If yes, set a global flag
(ans = false). - Return height =
1 + max(leftHeight, rightHeight)at each step. - Finally, return the
ansflag
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(h) recursion stack space (h=tree height)
Dry Run:
Function Call: isBalanced(root) where
root = TreeNode(1)
├── left: TreeNode(2)
│ └── left: TreeNode(4)
└── right: TreeNode(3)
Step 1:
→ Call calculateHeight(1)
Step 2:
→ Call calculateHeight(2)
Step 3:
→ Call calculateHeight(4)
Step 4:
→ Call calculateHeight(null) → return 0
→ Call calculateHeight(null) → return 0
→ Node 4 → leftHeight = 0, rightHeight = 0
→ |0 – 0| = 0 → OK
→ Return height = 1
Step 5:
→ Back to Node 2
→ leftHeight = 1
→ Call calculateHeight(null) → return 0
→ rightHeight = 0
→ |1 – 0| = 1 → OK
→ Return height = 2
Step 6:
→ Back to Node 1
→ leftHeight = 2
→ Call calculateHeight(3)
Step 7:
→ Call calculateHeight(null) → return 0
→ Call calculateHeight(null) → return 0
→ Node 3 → leftHeight = 0, rightHeight = 0
→ |0 – 0| = 0 → OK
→ Return height = 1
Step 8:
→ Back to Node 1
→ rightHeight = 1
→ |2 – 1| = 1 → OK
→ Return height = 3
Final Check:
→ Variable
Final Result: true
root = TreeNode(1)
├── left: TreeNode(2)
│ └── left: TreeNode(4)
└── right: TreeNode(3)
Step 1:
→ Call calculateHeight(1)
Step 2:
→ Call calculateHeight(2)
Step 3:
→ Call calculateHeight(4)
Step 4:
→ Call calculateHeight(null) → return 0
→ Call calculateHeight(null) → return 0
→ Node 4 → leftHeight = 0, rightHeight = 0
→ |0 – 0| = 0 → OK
→ Return height = 1
Step 5:
→ Back to Node 2
→ leftHeight = 1
→ Call calculateHeight(null) → return 0
→ rightHeight = 0
→ |1 – 0| = 1 → OK
→ Return height = 2
Step 6:
→ Back to Node 1
→ leftHeight = 2
→ Call calculateHeight(3)
Step 7:
→ Call calculateHeight(null) → return 0
→ Call calculateHeight(null) → return 0
→ Node 3 → leftHeight = 0, rightHeight = 0
→ |0 – 0| = 0 → OK
→ Return height = 1
Step 8:
→ Back to Node 1
→ rightHeight = 1
→ |2 – 1| = 1 → OK
→ Return height = 3
Final Check:
→ Variable
ans is still true → Tree is balancedFinal Result: true
var isBalanced = function(root) {
let ans = true;
let calculateHeight = (curr) => {
if(!curr) return 0;
let leftHeight = calculateHeight(curr.left);
let rightHeight = calculateHeight(curr.right);
if(Math.abs(leftHeight - rightHeight) > 1){
ans = ans && false;
}
return 1 + Math.max(leftHeight, rightHeight);
}
calculateHeight(root);
return ans;
};
class Solution:
def isBalanced(self, root):
self.ans = True
def calculateHeight(node):
if not node:
return 0
left = calculateHeight(node.left)
right = calculateHeight(node.right)
if abs(left - right) > 1:
self.ans = False
return 1 + max(left, right)
calculateHeight(root)
return self.ans
class Solution {
private boolean ans = true;
private int calculateHeight(TreeNode root) {
if (root == null) return 0;
int left = calculateHeight(root.left);
int right = calculateHeight(root.right);
if (Math.abs(left - right) > 1) {
ans = false;
}
return 1 + Math.max(left, right);
}
public boolean isBalanced(TreeNode root) {
calculateHeight(root);
return ans;
}
}
class Solution {
public:
bool ans = true;
int calculateHeight(TreeNode* root) {
if (!root) return 0;
int leftHeight = calculateHeight(root->left);
int rightHeight = calculateHeight(root->right);
if (abs(leftHeight - rightHeight) > 1) {
ans = false;
}
return 1 + max(leftHeight, rightHeight);
}
bool isBalanced(TreeNode* root) {
calculateHeight(root);
return ans;
}
};
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
int max(int a, int b) {
return (a > b) ? a : b;
}
int calculateHeight(TreeNode* root, bool* ans) {
if (!root) return 0;
int left = calculateHeight(root->left, ans);
int right = calculateHeight(root->right, ans);
if (abs(left - right) > 1) {
*ans = false;
}
return 1 + max(left, right);
}
bool isBalanced(TreeNode* root) {
bool ans = true;
calculateHeight(root, &ans);
return ans;
}
public class Solution {
private bool ans = true;
private int CalculateHeight(TreeNode root) {
if (root == null) return 0;
int left = CalculateHeight(root.left);
int right = CalculateHeight(root.right);
if (Math.Abs(left - right) > 1) {
ans = false;
}
return 1 + Math.Max(left, right);
}
public bool IsBalanced(TreeNode root) {
CalculateHeight(root);
return ans;
}
}
