Binary Tree Tilt: Post-Order DFS with Subtree Sums

You are given the root of a binary tree. Return the sum of every node's tilt, where the tilt of a node is the absolute difference between the sum of all values in its left subtree and the sum of all values in its right subtree.

This is LeetCode 563: Binary Tree Tilt, and it is one of those problems that looks simple on the surface but teaches you how post-order DFS can carry information upward through a tree. The technique you learn here applies to dozens of other tree problems.

The problem

Given the root of a binary tree, compute the tilt of every node and return their sum. The tilt of a node is defined as |left_subtree_sum - right_subtree_sum|. If a node has no left child, its left subtree sum is 0. If a node has no right child, its right subtree sum is 0. A null node has a tilt of 0.

Example 1: root = [1, 2, 3]. Node 2 has tilt |0 - 0| = 0. Node 3 has tilt |0 - 0| = 0. Node 1 has tilt |2 - 3| = 1. Total tilt = 1.

Example 2: root = [4, 2, 9, 3, 5, null, 7]. The total tilt is 15.

The approach

You need two things at every node: the sum of its left subtree and the sum of its right subtree. Once you have both, you can compute the tilt as the absolute difference and add it to a running total.

The natural way to get subtree sums is post-order DFS (left, right, then current node). You process the children first, so by the time you get to a node, you already know the sum of everything below it on each side. Each recursive call returns the full subtree sum (left_sum + right_sum + node.val) back to its parent.

Why bottom-up? Because the tilt at each node depends on information from its descendants. You cannot compute the tilt at the root without first knowing the sums of the entire left and right subtrees. Post-order traversal guarantees that children are fully processed before the parent.

The pattern is: your recursive function returns one value (subtree sum) to the parent, while also updating a separate accumulator (total tilt) as a side effect. This "return one thing, accumulate another" pattern is the same one you see in Diameter of Binary Tree and Binary Tree Maximum Path Sum.

The solution

def findTilt(root):
    total_tilt = 0

    def dfs(node):
        nonlocal total_tilt
        if not node:
            return 0
        left_sum = dfs(node.left)
        right_sum = dfs(node.right)
        total_tilt += abs(left_sum - right_sum)
        return left_sum + right_sum + node.val

    dfs(root)
    return total_tilt

Let's walk through each piece:

• total_tilt = 0 initializes the accumulator. Every node will add its tilt to this.
• if not node: return 0 is the base case. A null node contributes 0 to any subtree sum.
• left_sum = dfs(node.left) gets the total sum of everything in the left subtree.
• right_sum = dfs(node.right) gets the total sum of everything in the right subtree.
• total_tilt += abs(left_sum - right_sum) computes this node's tilt and adds it to the running total.
• return left_sum + right_sum + node.val sends the full subtree sum back up to the parent.

Step-by-step walkthrough

Let's trace the post-order DFS through [4, 2, 9, 3, 5, null, 7]. At each node, pay attention to two things: the subtree sum it returns to its parent and the tilt it adds to the running total.

The key moment is Step 3. At node 2, the left child returned 3 and the right child returned 5. The tilt is |3 - 5| = 2, and the subtree sum returned to the parent is 3 + 5 + 2 = 10. Then at Step 5, node 9 has no left child (sum 0) and a right child that returned 7. The tilt is |0 - 7| = 7. Finally at Step 6, the root sees left_sum = 10 and right_sum = 16, giving a tilt of 6. The total is 2 + 7 + 6 = 15.

Complexity analysis

Time is O(n). Every node is visited exactly once. At each node you do O(1) work (an addition, a subtraction, and an absolute value).

Space is O(h) where h is the height of the tree. That is the depth of the recursion stack. For a balanced tree, h = log n. For a completely skewed tree (all left children or all right children), h = n.

The building blocks

This problem is built on two fundamental building blocks:

1. Post-order subtree aggregation. The recursive function processes children first, then uses their results to compute something at the current node. The skeleton looks like this:

def solve(root):
    result = 0

    def dfs(node):
        nonlocal result
        if not node:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        result += AGGREGATE(left, right)
        return COMBINE(left, right, node.val)

    dfs(root)
    return result

For Binary Tree Tilt, AGGREGATE is abs(left - right) and COMBINE is left + right + node.val. For Diameter of Binary Tree, AGGREGATE is max(diameter, left + right) and COMBINE is 1 + max(left, right). Same skeleton, different details.

2. Recursive null base case. The if not node: return 0 base case terminates the recursion at null children. This is the same pattern you see in Maximum Depth of Binary Tree, Invert Binary Tree, and essentially every recursive tree solution. For subtree sum problems, returning 0 for null nodes means leaves naturally return their own value (0 + 0 + node.val).

The combination of these two building blocks gives you a clean, linear-time solution. You already know how to compute subtree sums recursively. The new thing is layering the tilt accumulation on top.

Edge cases

• Empty tree (root is None): return 0. The DFS is never called, and total_tilt stays at 0.
• Single node: return 0. Both children are null, so |0 - 0| = 0. A single node always has tilt 0.
• Skewed tree (all left or all right children): every node with one child has tilt equal to its child's subtree sum. The algorithm handles this correctly because the missing side returns 0.
• Perfectly balanced tree with equal subtrees: if left_sum equals right_sum at every node, the total tilt is 0. Each node's tilt is |x - x| = 0.
• Large values: the problem uses node values up to 10^4 with up to 10^4 nodes, so subtree sums fit comfortably in standard integers.

From understanding to recall

You just traced through the post-order DFS step by step. You understand why the function returns subtree sums but accumulates tilt separately. You see how the bottom-up approach gives each node exactly the information it needs. It all makes sense right now.

But when this problem comes up in practice, will you remember that dfs returns a subtree sum, not a tilt? Will you remember that the accumulation is abs(left_sum - right_sum) while the return value is left_sum + right_sum + node.val? Or will you mix them up and spend time debugging?

Understanding is not recall. You understood the solution. Recall means you can write it cold, under pressure, without second-guessing whether you return the tilt or the subtree sum.

Spaced repetition builds recall. You practice writing the solution from scratch at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the post-order pattern and the accumulator logic from memory. After a few repetitions, the pattern is automatic.

Related posts

• Diameter of Binary Tree - Uses the same "return one thing, accumulate another" pattern, but tracks depth instead of subtree sums.
• Balanced Binary Tree - Another post-order problem where you compute height bottom-up and check a condition at each node.
• Path Sum III - A more advanced subtree traversal problem where prefix sums replace simple aggregation.

The post-order DFS with accumulator pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling these patterns individually is far more effective than grinding random problems and hoping the techniques stick.