Balanced Binary Tree
Mahabharata — The Balanced Formation — No Flank Extends More Than One Level Beyond the Other
बाएं-दाएं अंतर — एक से अधिक नहीं। -1 लौटाओ असंतुलन पर — ऊपर संकेत दो॥
*Left-right difference — no more than one. Return -1 on imbalance — signal upward.*
The Story
Check if a binary tree is height-balanced (for every node, the height difference between left and right subtrees is at most 1).
For `[3,9,20,null,null,15,7]`: true. For `[1,2,2,3,3,null,null,4,4]`: false (height diff > 1 at root).
**Single-pass with -1 sentinel:** - Compute height recursively - If at any point |leftHeight - rightHeight| > 1, return -1 (sentinel for 'unbalanced') - If a subtree returns -1, propagate -1 upward (don't compute further)
```java public boolean isBalanced(TreeNode root) { return height(root) != -1; }
int height(TreeNode root) { if (root == null) return 0; int left = height(root.left); if (left == -1) return -1; // Left unbalanced → propagate int right = height(root.right); if (right == -1) return -1; // Right unbalanced → propagate if (Math.abs(left - right) > 1) return -1; // This node unbalanced return 1 + Math.max(left, right); // Return actual height } ```
Trace `[1,2,2,3,3,null,null,4,4]`: - height(4) = 1 (leaf) - height(3 with child 4) = 2 - height(2 with children 3,3) = left=2, right=height(3-no-child-3)... let me check: [1,2,2,3,3,null,null,4,4] - 2.left=3, 2.right=3. 3.left=4, 3.right=4. 2-right side: 2.right=2, 2.right.left=null, etc. - Eventually the root has left-height=4, right-height=2 → |4-2|>1 → return -1 → isBalanced=false ✓
The isBalanced-at-Every-Node Approach
For each node: check |height(left)-height(right)|≤1 AND recurse. O(n²) due to repeated height computations.
// O(n²) — computes height multiple times for same nodes
public boolean isBalancedBrute(TreeNode root) {
if (root == null) return true;
int lh = heightBrute(root.left), rh = heightBrute(root.right);
return Math.abs(lh-rh) <= 1 && isBalancedBrute(root.left) && isBalancedBrute(root.right);
}
int heightBrute(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(heightBrute(root.left), heightBrute(root.right));
}The -1 Sentinel Single-Pass Wisdom
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
int height(TreeNode root) {
if (root == null) return 0;
int left = height(root.left);
if (left == -1) return -1;
int right = height(root.right);
if (right == -1) return -1;
if (Math.abs(left - right) > 1) return -1;
return 1 + Math.max(left, right);
}Step-by-Step Walkthrough
Null: return 0. ✅ Leaf [1]: height=1. |0-0|=0≤1 → return 1. isBalanced=true ✅
Deep Insight
**The -1 sentinel trick:** Instead of returning a boolean + height (which would require a pair or global variable), we repurpose the return value: negative means unbalanced. This single-pass approach avoids recomputing heights.
**O(n) vs O(n²):** The brute force computes height for each subtree multiple times. The single-pass approach computes each node's height exactly once while simultaneously checking balance. The -1 propagation allows early termination.
**Foundation:** This pattern (return -1 to indicate failure in a height computation) is reused in tr-21 (Diameter) and other tree validation problems.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(h) | height() computed multiple times per node |
| Optimal | O(n) | O(h) | Single post-order pass with -1 sentinel |
Pattern Recognition
✅ Balanced tree: single-pass height with -1 sentinel ✅ Return -1 if unbalanced; actual height if balanced ✅ Short-circuit: if left==-1 or right==-1, propagate -1 ✅ O(n) vs O(n²) brute force **LeetCode Trigger Phrases:** → "balanced binary tree" → Height-balanced check → Single-pass with sentinel value pattern
Bhagavad Gita 12.18
समः शत्रौ च मित्रे च तथा मानापमानयोः। शीतोष्णसुखदुःखेषु समः सङ्गविवर्जितः॥
Equal to enemy and friend, equal in honor and dishonor, equal in cold and heat, pleasure and pain, free from attachment.
Connection: A balanced binary tree maintains equanimity at every node — neither the left nor the right subtree exceeds the other by more than one level. Like the Gita's description of the equanimous sage who remains balanced through all pairs of opposites, the balanced tree maintains its structural dharma at every node. The moment any node breaks this balance, the -1 sentinel propagates upward like a warning that equanimity has been violated.