Binary Tree Tilt

Problem Statement

The task is to compute the sum of the tilts for all nodes in a binary tree. A node's tilt is defined as the absolute difference between the sum of the values in its left subtree and the sum of the values in its right subtree. If a node lacks a left or right child, the corresponding subtree sum is considered to be 0. The problem requires calculating the sum of these tilts for the entire tree, starting from its root.

Examples

Example 1

Input:

root = [1,2,3]

Output:

1

Explanation:

Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1

Example 2

Input:

root = [4,2,9,3,5,null,7]

Output:

15

Explanation:

Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 5 : |0-0| = 0 (no children)
Tilt of node 7 : |0-0| = 0 (no children)
Tilt of node 2 : |3-5| = 2 (left subtree is just left child, so sum is 3; right subtree is just right child, so sum is 5)
Tilt of node 9 : |0-7| = 7 (no left child, so sum is 0; right subtree is just right child, so sum is 7)
Tilt of node 4 : |(3+5+2)-(9+7)| = |10-16| = 6 (left subtree values are 3, 5, and 2, which sums to 10; right subtree values are 9 and 7, which sums to 16)
Sum of every tilt : 0 + 0 + 0 + 2 + 7 + 6 = 15

Example 3

Input:

root = [21,7,14,1,1,2,2,3,3]

Output:

9

Constraints

• The number of nodes in the tree is in the range [0, 104].
• -1000 <= Node.val <= 1000

Approach and Intuition

To solve this problem, you can adopt a recursive depth-first search (DFS) strategy. Here's a step-by-step breakdown of the approach:

1. Define a recursive function that computes the total sum of all node values for a given subtree. During this computation, calculate the tilt of the current node.

2. For each node:

   • Recursively calculate the sum of values in the left subtree.
   • Recursively calculate the sum of values in the right subtree.

3. Compute the tilt for the current node as the absolute difference between the sums obtained from the left and right subtrees.

4. Accumulate the tilt of the current node to a global variable which keeps track of the sum of all tilts.

5. Return the sum of node values of the current subtree (to its parent), which is used to compute the tilt at the parent node.

Through this recursive function, each node's tilt is calculated using its children's subtree sums, and simultaneously, these sums are computed and propagated up the tree. This efficient recursion ensures that each node's value is used exactly once for tilt calculation and once for subtree sum computation, leading to an optimal solution with respect to time complexity.

Solutions

class Solution {
    private int totalTiltValue = 0;
    
    private int sumValues(TreeNode currentNode) {
        if (currentNode == null)
            return 0;
    
        int leftValueSum = this.sumValues(currentNode.left);
        int rightValueSum = this.sumValues(currentNode.right);
        int currentTilt = Math.abs(leftValueSum - rightValueSum);
        this.totalTiltValue += currentTilt;
    
        return currentNode.val + leftValueSum + rightValueSum;
    }
    
    public int findTilt(TreeNode rootNode) {
        this.totalTiltValue = 0;
        this.sumValues(rootNode);
        return this.totalTiltValue;
    }
}