deepSWE.io

Binary Tree Tilt

Trees

Problem Statement

Given the `root` of a binary tree, return the sum of every 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 there the node does not have a right child.

Example

Output: 15

Algorithm Explanation

We can solve this problem with a single pass using a post-order traversal (DFS). For each node, we need to calculate the sum of its left and right subtrees to find its tilt.

Algorithm Steps

DFS Function: Create a recursive DFS function that returns the sum of the subtree rooted at the current node.
Post-order Traversal: In our DFS, we'll first visit the left and right children, then process the current node.
Calculate Tilt: After the recursive calls return the sums of the left and right subtrees, we can calculate the tilt for the current node as `abs(left_sum - right_sum)`. We add this to a running total.
Return Subtree Sum: The DFS function for a node should return `node.val + left_sum + right_sum`.

Start

Starting DFS from the root.

Total Tilt: 0

Binary Tree Tilt Solution


class Solution:
    def findTilt(self, root: Optional[TreeNode]) -> int:
        self.total_tilt = 0
        
        def value_sum(node):
            if not node:
                return 0
            
            left_sum = value_sum(node.left)
            right_sum = value_sum(node.right)
            
            tilt = abs(left_sum - right_sum)
            self.total_tilt += tilt
            
            return node.val + left_sum + right_sum

        value_sum(root)
        return self.total_tilt