---

1. Problem Summary

You are given the root of a binary tree.
Your task is to compute the total tilt of the tree, where:

• The tilt of a node is defined as:

abs(sum of values in left subtree − sum of values in right subtree)

• The tilt of the whole tree is the sum of tilts of all nodes.

Important details:

• A leaf node has tilt 0 because both subtree sums are 0
• Subtree sums must include all descendant nodes
• You must return a single integer representing total tilt

Example interpretation:
If a node has left subtree sum = 10 and right subtree sum = 4, its tilt is:

|10 − 4| = 6

---

2. Key Insights

Subtree sums must be computed for every node

Tilt depends on complete subtree totals, not direct children.

Post-order traversal is required

We must compute:

1. left subtree sum
2. right subtree sum
3. tilt at node
4. return node total sum upward

We accumulate tilt during recursion

Maintain a global or external tracker to accumulate tilt values.

Each node returns:

sum of (left subtree + right subtree + node value)

This allows parent nodes to compute their tilt using returned sums.

---

3. Approach

Depth-first post-order recursion

Steps:

1. Initialize global tilt accumulator.
2. Define recursive function that:
   • if node is null → return 0
   • recursively compute left sum
   • recursively compute right sum
   • compute tilt = abs(leftSum – rightSum)
   • add tilt to global accumulator
   • return total subtree sum
3. Call recursion on root.
4. Return accumulated tilt.

This ensures tilt contributions are gathered bottom-up.

---

4. Time and Space Complexity

Time Complexity: O(N)

Every node is visited exactly once.

Space Complexity:

• O(H) recursion depth
• worst case skewed tree → O(N)
• best case balanced tree → O(log N)

---

5. Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    private int totalTilt = 0;

    public int findTilt(TreeNode root) {
        computeSum(root);
        return totalTilt;
    }

    private int computeSum(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftSum = computeSum(node.left);
        int rightSum = computeSum(node.right);

        totalTilt += Math.abs(leftSum - rightSum);

        return leftSum + rightSum + node.val;
    }
}

---

6. Dry Run Examples

Example 1

Input Tree:

      1
     / \
    2   3

Step-by-step:

Node 2:
left sum = 0
right sum = 0
tilt = |0−0| = 0

Node 3:
tilt = 0

Node 1:
left sum = 2
right sum = 3
tilt = |2−3| = 1

Total tilt = 0 + 0 + 1 = 1

Output:

1

---

Example 2

Input Tree:

        4
       / \
      2   9
     / \   \
    3   5   7

Compute subtree sums:

Node 3 tilt = 0
Node 5 tilt = 0
Node 2 tilt = |3−5| = 2
Node 7 tilt = 0
Node 9 tilt = |0−7| = 7
Node 4 tilt = |(3+5+2) − (9+7)| = |10 − 16| = 6

Total tilt:

0 + 0 + 2 + 0 + 7 + 6 = 15

Output:

15

---

Example 3 (single node)

[5]

Tilt = 0

---

Example 4 (linked chain)

1
 \
  2
   \
    3

Tilts:
Node 3 = 0
Node 2 = |0−3| = 3
Node 1 = |0−5| = 5

Total tilt = 8

---

7. Why This Solution Works

• Computes subtree sums correctly via post-order traversal
• Avoids recomputation (no repeated sum scanning)
• Uses accumulator to aggregate node tilts cleanly
• Works for all binary tree shapes
• Efficient and minimal logic

---

8. Common Mistakes

1. Computing subtree sums repeatedly (O(N²) slowdown)
2. Incorrect tilt definition (using children instead of full subtree sums)
3. Forgetting to accumulate tilt globally
4. Using preorder or inorder traversal incorrectly
5. Returning tilt instead of subtree sum from recursion