Sponsored
Sponsored
This approach involves recursively calculating the height of each subtree and checking if the subtrees are balanced by ensuring the difference in height is not more than one.
Time Complexity: O(N^2), where N is the number of nodes in the tree, as we recalculate the height of subtrees multiple times. Space Complexity: O(N) due to recursion stack.
1function TreeNode(val) {
2 this.val = val;
3 this.left = this.right = null;
4}
5
6function isBalanced(root) {
7 if (root === null) return true;
8
9 function height(node) {
10 if (node === null) return 0;
11 return Math.max(height(node.left), height(node.right)) + 1;
12 }
13
14 const leftHeight = height(root.left);
15 const rightHeight = height(root.right);
16
17 return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
18}JavaScript uses a recursive function height to evaluate the height of nodes. The isBalanced function uses this information to ensure that subtree height differences are within acceptable range, checking recursively.
This optimized approach calculates the height and balance status of a tree in a single recursive function, thus avoiding recalculations by returning both height and balanced status in form of tuples or objects.
Time Complexity: O(N). Space Complexity: O(N), which includes the recursion stack depth.
1public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public bool IsBalanced(TreeNode root) {
return CheckBalance(root).balanced;
}
private (int height, bool balanced) CheckBalance(TreeNode node) {
if (node == null) return (0, true);
var left = CheckBalance(node.left);
if (!left.balanced) return (0, false);
var right = CheckBalance(node.right);
if (!right.balanced) return (0, false);
bool balanced = Math.Abs(left.height - right.height) <= 1;
return (Math.Max(left.height, right.height) + 1, balanced);
}
}The C# version leverages value tuples to hold height and balance, optimizing checks and halting recursive calls promptly, conserving computational resources upon imbalance revelation.