LeetCode #563 Easy

Binary Tree Tilt

Sum the tilt of every node, where a node's tilt is |sum(left subtree) - sum(right subtree)|.

treedfsrecursion

02

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.

03

Approach

1

Recurse for subtree sums

Each call to subtreeSum(node) returns node.val + subtreeSum(node.left) + subtreeSum(node.right) -- purely the sum, nothing about tilt.

2

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).

3

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.

04

Solution & live demo

python

▶1class Solution:
▶2    def findTilt(self, root):
▶3        total_tilt = 0
▶4 
▶5        def subtree_sum(node):
▶6            nonlocal total_tilt
▶7            if not node:
▶8                return 0
▶9            left_sum = subtree_sum(node.left)
▶10            right_sum = subtree_sum(node.right)
▶11            total_tilt += abs(left_sum - right_sum)
▶12            return node.val + left_sum + right_sum
▶13 
▶14        subtree_sum(root)
▶15        return total_tilt

05

Edge cases

Empty tree

subtreeSum(None) returns 0, contributing nothing to any tilt.

Leaf node

Both subtree sums are 0, so its tilt is 0 -- but it still returns its own value upward.

All values on one side (skewed tree)

Each node's tilt is large since one side is always 0, but the sums still combine correctly bottom-up.

Negative values

Sums and tilt (via abs) still compute correctly; no special casing needed.

06

Complexity

Time

O(n)

Space

O(h)

One post-order pass computes every subtree sum exactly once.