Binary Tree Tilt
Binary Tree Tilt: sum the tilt of every node, where a node's tilt is |sum(left subtree) - sum(right subtree)|.
- The number of nodes in the tree is in the range [0, 10⁴].
- -1000 <= Node.val <= 1000
Intuition
Binary tree tilt sums the tilt of every node, where a node's tilt is the absolute difference between its left and right subtree sums. Two quantities are in play, and confusing them is the whole difficulty.
The instinct is to have the recursion return the tilt. That fails immediately, because a parent computing its own tilt needs its children's subtree sums, not their tilts. Returning tilt upward starves the parent of the one thing it requires.
So the recursion returns the sum, and the tilt is collected on the side:
- Return the subtree sum upward; accumulate the tilt into a total held outside the recursion.
That is the same split as Diameter of Binary Tree, where the function returns depth while recording the diameter separately, and Maximum Path Sum, where it returns the extendable gain while recording the bending candidate. Recognising the pattern makes all three one technique.
At each node: get both child sums, add abs(leftSum − rightSum) to the running total, then return leftSum + rightSum + node.val.
A null node returns 0, which makes a leaf's tilt abs(0 − 0) = 0 — correct, since a leaf has no subtrees to differ.
The tilt total is never part of a return value. It lives in a variable outside the recursion and is read once at the end.
One postorder pass that returns subtree sums while accumulating tilts as a side effect. Tilt measures lopsidedness, so it is a useful lens on balancing binary trees even though it never rebalances anything. 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
Before reading on: price up what plain recursion costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(h) space.
Separate the two quantities
The recursion returns the subtree sum; the tilt is accumulated separately. A parent needs its children's sums to compute its own tilt, so returning tilt upward would starve it of exactly what it needs.
Return zero for a null node
An empty subtree sums to 0. This makes a leaf's tilt abs(0 - 0) = 0, which is correct without any special case for leaves.
Compute the tilt at each node
With both child sums in hand, add abs(leftSum - rightSum) to a total held outside the recursion. This is the only place the answer is written.
Return the sum upward
Return leftSum + rightSum + node.val so the parent can compute its own tilt. The tilt total is never returned — mixing the two is the mistake this problem is built around.
Recognise the shared pattern
Diameter of Binary Tree returns depth while recording diameter; Maximum Path Sum returns gain while recording the bend. Same structure, different quantities — naming it makes all three familiar.
Cost of the traversal
Every node is visited once with O(1) work, giving O(n) time. Space is O(h) for the recursion stack — O(log n) balanced, O(n) on a skewed tree.
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.