Binary Tree Tilt
MediumReturn the subtree sum, accumulate the tilt
Problem
Return the sum over all nodes of the absolute difference between left-subtree sum and right-subtree sum.
Each node's tilt is the gap between its two subtree sums; add all tilts together.
The idea
Each node's tilt is the absolute difference of its two subtree sums, so return the sum upward while adding the tilt to a running total. One postorder pass produces both.
The trick
- Return the sum, accumulate the tilt in an outer variable.
- A node's own value belongs in the sum it returns, not in its tilt.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [1,2,3] Values: 1, 2, 3.
1dfs returns subtree sum2tilt += abs(leftSum - rightSum)Input
- array
- [1, 2, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [1,2,3]
- Output:
- 1
- Explanation:
- Tilts: |0-0|,|0-0|, and |2-3| at root → 1.
Example 2
- Input:
- tree = [4,2,9,3,5,null,7]
- Output:
- 15
- Explanation:
- Sum of every node's left-right subtree-sum gap → 15.
Example 3
- Input:
- tree = [1]
- Output:
- 0
- Explanation:
- A leaf has tilt 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.