Leet code problem 563: Binary Tree Tilt

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 1:

The goal of this problem is to find the "tilt" of a binary tree, which is defined as the absolute difference in the sums of values in the left and right subtrees for each node in the tree. To do this, the algorithm implements a post-order traversal technique, which analyses the nodes of the tree in the following order: first, the left subtree, then the right, and finally, the current node. The process starts with the findTilt function, which takes the binary tree's root node as input.

There is a tilt_counter variable inside the findTilt function that is set to 0 and maintains track of the cumulative tilt for the entire tree. The code includes a recursive function named post_order_traversal, which traverses the binary tree using the post-order algorithm.If a node is null (indicating there is no node), this function returns 0.

post_order_traversal computes the sums of values in the left and right subtrees by performing recursive calls to itself for the current node's left and right children. These totals are kept in the variables left_sum and right_sum. The method calculates the absolute difference between left_sum and right_sum and accumulates this tilt in the tilt_counter variable to determine the tilt of the current node. Finally, the method returns the total of values for the current node and its subtrees, calculated as left_sum + right_sum + node.val.

The findTilt function executes the post_order_traversal function using the root node of the tree to do the post-order traversal, as defined in the function declaration. The binary tree's overall tilt accumulates in the tilt_counter variable, which is returned by the findTilt method.

In essence, this code calculates the total tilt of a binary tree carefully using a post-order recursive traversal, determining the tilt for each node and storing the results in the tilt_counter. The final result indicates the total tilt of the binary tree.

Code in Javascript

var findTilt = (root) => {
    let tilt_counter = 0;
    const post_order_traversal = (node) => {

        // If the node does not exist.
        // It has no value and therefore it's a 0.
        if (!node) {
            return 0;
        }

        // Post Order, get me their SUMS!!!
        let left_sum  = post_order_traversal(node.left);
        let right_sum = post_order_traversal(node.right);

        // Figure out the difference between the left and right subtrees
        // We use the absolute value of the difference to keep track of the tilt
        tilt_counter += Math.abs(left_sum - right_sum);

        // Return the value of the node and it's subtrees.
        return left_sum + right_sum + node.val;
    };

    post_order_traversal(root);
    return tilt_counter;
};

Code in Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTilt(self, root: Optional[TreeNode]) -> int:
        tilt_counter = 0

        def post_order_traversal(node):
            """
            Perform post-order traversal to calculate the tilt of each node.

            Args:
                node: The current node being traversed.

            Returns:
                The sum of the node and its subtrees.
            """
            if not node:
                # If the node does not exist, return 0.
                # It has no value and therefore it's a 0.
                return 0

            # Post Order, get me their SUMS!!!
            left_sum = post_order_traversal(node.left)
            right_sum = post_order_traversal(node.right)

            # Figure out the difference between the left and right subtrees
            # We use the absolute value of the difference to keep track of the tilt
            nonlocal tilt_counter
            tilt_counter += abs(left_sum - right_sum)

            # Return the value of the node and its subtrees.
            return left_sum + right_sum + node.val

        post_order_traversal(root)
        return tilt_counter