Binary Tree Tilt

Binary Tree Tilt

What is this problem about?

The tilt of a tree node is defined as the absolute difference between the sum of all node values in its left subtree and the sum of all node values in its right subtree. The total tilt of a binary tree is the sum of the tilts of all its nodes. The Binary Tree Tilt coding problem asks you to calculate this total sum.

Why is this asked in interviews?

This problem, often seen in Amazon and Indeed interviews, is a great test of recursive data aggregation. It requires you to calculate two different things simultaneously: the sum of nodes (to pass up to the parent) and the tilt (to add to a global total). It’s an exercise in maintaining a running total while performing a standard tree traversal.

Algorithmic pattern used

This problem is solved using a Post-order Traversal (DFS). To calculate the tilt of a node, you must first know the sum of its left and right subtrees. Therefore, your recursive function should return the total sum of the subtree rooted at the current node (left_sum + right_sum + node.val). While calculating this, you compute the tilt (abs(left_sum - right_sum)) and add it to a global variable.

Example explanation

Consider a simple tree: 4 / 2 9 / \
3 5 7

1. For node 3: Tilt is |0-0| = 0. Sum is 3.
2. For node 5: Tilt is |0-0| = 0. Sum is 5.
3. For node 2: Tilt is |3-5| = 2. Sum is 3+5+2 = 10.
4. For node 7: Tilt is |0-0| = 0. Sum is 7.
5. For node 9: Tilt is |0-7| = 7. Sum is 0+7+9 = 16.
6. For root 4: Tilt is |10-16| = 6. Sum is 10+16+4 = 30. Total Tilt = 0 + 0 + 2 + 0 + 7 + 6 = 15.

Common mistakes candidates make

A common pitfall is confusing the "sum of nodes" with the "sum of tilts." The recursive function should return the sum of the values in the subtree, not the tilt. Another mistake is forgetting that tilt is the absolute difference—candidates sometimes forget to use an abs() function, leading to incorrect results when one subtree is larger than the other.

Interview preparation tip

When a problem asks for a value based on subtree sums, always think "Post-order DFS." Practice returning one value while updating a global state, as this is a recurring theme in tree-based interview questions.