LeetCode: 563. Binary Tree Tilt

The Problem

Given the root of a binary tree, return the sum of every tree node's tilt.

The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values. If a node does not have a left child, then the sum of the left subtree node values is treated as 0. The rule is similar if the node does not have a right child.

Example

Input:  [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

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

int findTilt(TreeNode* root) {
    int total = 0;
    sumTilt(root, total);
    return total;
}

int sumTilt(TreeNode *node, int &total) {
    if (node == nullptr) return 0;

    int left_sum = sumTilt(node->left, total);
    int right_sum = sumTilt(node->right, total);

    total += abs(left_sum - right_sum);

    return node->val + left_sum + right_sum;
}

Here's how it works:

The sumTilt function is a recursive helper function that calculates both the sum of values of subtrees and the tilt. It takes two parameters: a pointer to a TreeNode (TreeNode *node) and a reference to the total variable (int &total).

• The first line checks if the current node is nullptr, which means it's a leaf node or an empty node. If so, it returns 0, indicating that the sum of values for this subtree is 0.
• If the node is not nullptr, it recursively calls sumTilt on its left and right children and stores their returned values in left_sum and right_sum.
• Then, it calculates the tilt of the current node by taking the absolute difference between left_sum and right_sum, and adds it to the total variable. This way, total keeps accumulating the total tilt of the entire tree.
• Finally, it returns the sum of values of the current node, plus the left_sum and right_sum, which represents the total sum of values for the current subtree.

The findTilt function initializes the total variable, calls the sumTilt function on the root of the tree, and then returns the total tilt of the entire binary tree.