Binary Tree Tilt
Add up the tilt of every node, where a node's tilt is how far apart the value sums of its left and right subtrees are: |left sum − right sum|.
Examples
Tilt of node 2: |0-0| = 0. Tilt of node 3: |0-0| = 0. Tilt of node 1: |2-3| = 1. Total = 0 + 0 + 1 = 1.
Tilt of node 3: 0. Tilt of node 5: 0. Tilt of node 7: 0. Tilt of node 2: |3-5| = 2. Tilt of node 9: |0-7| = 7. Tilt of node 4: |(3+5+2) - (9+7)| = |10 - 16| = 6. Total = 0+0+0+2+7+6 = 15.
Problem Understanding
The Tilt of a tree node is defined as abs(sum(left_subtree) - sum(right_subtree)).
The Total Tilt of the tree is the sum of tilts of all nodes.
We need to traverse the tree, and for every node, compute the sum of its left and right children to find its tilt, while also returning the sum to its parent.
Algorithm Strategy (Post-Order)
We use Post-Order DFS (Bottom-Up).
- Return Value: the sum of the values in the subtree, so the parent can compute its own tilt.
- Side Effect: while computing the sum, add the node’s tilt to
total.
Logic:
left = valueSum(node.left)right = valueSum(node.right)total += abs(left - right)- return
node.val + left + right
Interactive Visualization
Under each finished node are both numbers: Σ, the subtree sum it returns to its parent, and t, its own tilt, which only ever goes into total.
Dry Run: [4, 2, 9, 3, 5, null, 7]
Tree: [4, 2, 9, 3, 5, null, 7]
| Node | Left sum | Right sum | Tilt = abs(left − right) | total after | Returns node + left + right |
|---|---|---|---|---|---|
| 3 | 0 | 0 | 0 | 0 | 3 |
| 5 | 0 | 0 | 0 | 0 | 5 |
| 2 | 3 | 5 | 2 | 2 | 2 + 3 + 5 = 10 |
| 7 | 0 | 0 | 0 | 2 | 7 |
| 9 | 0 | 7 | 7 | 9 | 9 + 0 + 7 = 16 |
| 4 | 10 | 16 | 6 | 15 | 4 + 10 + 16 = 30 |
Result: total tilt 15.
Edge Cases & Common Mistakes
- Empty Tree: Return 0. The tilt of a null node is undefined/0.
- Single Node: Left sum 0, Right sum 0. Tilt is 0.
- Negative Values: Tilt is
abs(left - right), so negative sums work fine. Example: Left sum -5, Right sum -2, Tilt = |-5 - (-2)| = |-3| = 3. - Mistake - Returning Tilt: Do NOT return the tilt from the recursive function. You must return the sum of values so the parent can calculate its own tilt.
Solution
Post-order traversal with a global accumulator.
Binary Tree Tilt Code
1var findTilt = function(root) {2 let total = 0;34 function valueSum(node) {5 if (!node) return 0;6 const left = valueSum(node.left);7 const right = valueSum(node.right);8 total += Math.abs(left - right);9 return node.val + left + right;10 }1112 valueSum(root);13 return total;14};