Binary Tree Tilt
Sum the tilt of every node, where a node's tilt is |sum(left subtree) - sum(right subtree)|.
Open on LeetCode ↗Intuition
Trying to make the recursion return the tilt directly is the wrong instinct -- the recursion's job is to return the SUBTREE SUM, because that is what a parent node needs to compute ITS OWN tilt. The tilt itself is a side quantity: compute it at each node from the two subtree sums just returned, then accumulate it into an outer running total, separately from whatever gets passed back up the call stack. Two different values are flowing in two different directions at once -- sums flow upward through return values, while the tilt total accumulates sideways as a side effect -- and keeping them distinct is the entire problem.
One postorder pass that returns subtree sums while accumulating tilts as a side effect. The function's return value and the answer it builds are different quantities — a common shape when a parent needs an aggregate its children computed.
Approach
Recurse for subtree sums
Each call to subtreeSum(node) returns node.val + subtreeSum(node.left) + subtreeSum(node.right) -- purely the sum, nothing about tilt.
Compute and accumulate tilt as a side effect
At each node, tilt = abs(leftSum - rightSum); add it into a total tracked outside the recursion's return value (an instance variable or nonlocal counter).
Return only the sum upward
The function returns leftSum + rightSum + node.val so the parent can use it -- the tilt total is never part of what gets returned.
Solution & live demo
Common pitfalls
Returning the tilt instead of the sum
return abs(left_sum - right_sum)
return node.val + left_sum + right_sum
The parent needs its children's sums to compute its own tilt. Returning the tilt gives it the wrong quantity and every level above is computed from nonsense.
Omitting the node's own value from the sum
return left_sum + right_sum
return node.val + left_sum + right_sum
A subtree's sum includes its root. Leaving it out makes every leaf report 0 and the tilts collapse toward zero throughout the tree.
Recomputing subtree sums per node
tilt += abs(sumTree(node.left) - sumTree(node.right)) # with sumTree walking each subtree
left_sum = subtree_sum(node.left)
Calling a separate sum helper at every node re-walks the same subtrees, giving O(n²) on a skewed tree. Returning the sum from the same recursion computes it once.
Edge cases
subtreeSum(None) returns 0, contributing nothing to any tilt.
Both subtree sums are 0, so its tilt is 0 -- but it still returns its own value upward.
Each node's tilt is large since one side is always 0, but the sums still combine correctly bottom-up.
Sums and tilt (via abs) still compute correctly; no special casing needed.