Binary Tree Tilt
Mahabharata — The Imbalance Score — Sum of All Nodes' Absolute Left-Right Differences
हर नोड का झुकाव — |बाएं योग − दाएं योग|। सभी झुकावों का योग — वृक्ष का कुल झुकाव॥
*Each node's tilt — |left sum − right sum|. Sum of all tilts — total tilt of the tree.*
The Story
The **tilt** of a node = |sum of all node values in its left subtree − sum of all node values in its right subtree|. Return the sum of all nodes' tilts.
For `[1,2,3]`: tilt(2)=0+0=0, tilt(3)=0, tilt(1)=|2-3|=1. Total=1. For `[4,2,9,3,5,null,7]`: answer=15.
**Post-order: return subtree sum, accumulate tilt:** ```java int totalTilt = 0;
public int findTilt(TreeNode root) { sum(root); return totalTilt; }
int sum(TreeNode root) { if (root == null) return 0; int left = sum(root.left); // Sum of left subtree int right = sum(root.right); // Sum of right subtree totalTilt += Math.abs(left - right); // Add this node's tilt return root.val + left + right; // Return total sum including this node } ```
Trace `[4,2,9,3,5,null,7]`: - sum(3)=3, tilt(3)=0 - sum(5)=5, tilt(5)=0 - sum(2): left=3,right=5. tilt(2)=|3-5|=2. return 2+3+5=10 - sum(7)=7, tilt(7)=0 - sum(9): left=0,right=7. tilt(9)=|0-7|=7. return 9+0+7=16 - sum(4): left=10,right=16. tilt(4)=|10-16|=6. return 4+10+16=30 - Total tilt = 0+0+2+0+7+6 = 15 ✓
The Separate Sum Computation
For each node: compute subtree sums separately. O(n²).
// O(n²): compute sum for each node's subtrees separately
int findTiltBrute(TreeNode root) {
if (root == null) return 0;
int tilt = Math.abs(subtreeSum(root.left) - subtreeSum(root.right));
return tilt + findTiltBrute(root.left) + findTiltBrute(root.right);
}
int subtreeSum(TreeNode root) {
if (root == null) return 0;
return root.val + subtreeSum(root.left) + subtreeSum(root.right);
}The Post-Order Sum+Tilt Accumulation
int totalTilt = 0;
public int findTilt(TreeNode root) {
sum(root);
return totalTilt;
}
int sum(TreeNode root) {
if (root == null) return 0;
int left = sum(root.left);
int right = sum(root.right);
totalTilt += Math.abs(left - right);
return root.val + left + right;
}Step-by-Step Walkthrough
Null tree: return 0, tilt=0 ✅ Single node [5]: left=0,right=0. tilt+=|0-0|=0. return 5. findTilt=0 ✅
Deep Insight
**Pattern: single post-order pass for two purposes.** The sum() function computes subtree sums (returned) AND accumulates tilt (side effect via global). This is the same pattern as tr-21 (Diameter) where height() computed heights and updated maxDiam.
This pattern appears frequently: when you need to aggregate something during a bottom-up computation, use a global variable + a post-order helper that returns what parent nodes need.
**Why post-order?** We need subtree sums before computing the current node's tilt. Post-order processes children first, then the current node.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(h) | subtreeSum computed at each node |
| Optimal | O(n) | O(h) | Single post-order pass |
Pattern Recognition
✅ Tilt: post-order returning sum + updating global tilt ✅ |left_sum - right_sum| at each node ✅ Return val+left+right for parent to use ✅ Same pattern as diameter: global update + height return **LeetCode Trigger Phrases:** → "binary tree tilt" → Sum of absolute differences of subtree sums → Post-order with global accumulation
Bhagavad Gita 12.17
यो न हृष्यति न द्वेष्टि न शोचति न काङ्क्षति। शुभाशुभपरित्यागी भक्तिमान्यः स मे प्रियः॥
One who neither rejoices nor grieves, who neither laments nor desires, who renounces both good and bad — such a devotee is dear to Me.
Connection: The tilt of a binary tree measures the imbalance — the absolute difference between what exists on the left versus the right. A tree with zero tilt everywhere would be perfectly equanimous. The algorithm accumulates these imbalances across all nodes, revealing the tree's total structural bias. Like the Gita's description of the beloved devotee who is equally unmoved by fortune and misfortune, a perfect binary tree strives for zero tilt — but most trees, like most beings, carry the accumulated weight of their asymmetries.