Binary Tree Tilt

Difficulty: Easy | Acceptance: 65.80% | Paid: No Topics: Tree, Depth-First Search, Binary Tree

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 the sum of 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.

• Examples
• Constraints
• Post-order Traversal (DFS)
• Brute Force with Helper Function

Examples

Example 1

Input: root = [1,2,3]
Output: 1
Explanation: 
Tilt of node 2 : |0-0| = 0
Tilt of node 3 : |0-0| = 0
Tilt of node 1 : |2-3| = 1
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
Tilt of node 5 : |0-0| = 0
Tilt of node 7 : |0-0| = 0
Tilt of node 2 : |3-5| = 2
Tilt of node 9 : |0-7| = 7
Tilt of node 4 : |(3+5+2)-(9+7)| = |10-16| = 6
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, 10⁴].
-1000 <= Node.val <= 1000

Post-order Traversal (DFS)

Intuition Use post-order traversal to compute subtree sums bottom-up, calculating each node’s tilt while returning the sum to parent nodes.

Steps

• Traverse the tree in post-order (left, right, root)
• For each node, get the sum of left and right subtrees
• Calculate the tilt as absolute difference and add to total
• Return the total sum of subtree rooted at current node

# 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: TreeNode) -> int:
        self.total_tilt = 0
        
        def dfs(node):
            if not node:
                return 0
            
            left_sum = dfs(node.left)
            right_sum = dfs(node.right)
            
            tilt = abs(left_sum - right_sum)
            self.total_tilt += tilt
            
            return node.val + left_sum + right_sum
        
        dfs(root)
        return self.total_tilt

Complexity

• Time: O(n) where n is the number of nodes
• Space: O(h) where h is the height of the tree (recursion stack)
• Notes: Optimal single-pass solution

Brute Force with Helper Function

Intuition For each node, separately calculate the sum of left and right subtrees using a helper function, then compute the tilt.

Steps

• Create a helper function to calculate subtree sum
• For each node, get left and right subtree sums
• Calculate tilt and recursively process children
• Sum up all tilts across the tree

# 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: TreeNode) -> int:
        def subtree_sum(node):
            if not node:
                return 0
            return node.val + subtree_sum(node.left) + subtree_sum(node.right)
        
        def calculate_tilt(node):
            if not node:
                return 0
            left_sum = subtree_sum(node.left)
            right_sum = subtree_sum(node.right)
            return abs(left_sum - right_sum) + calculate_tilt(node.left) + calculate_tilt(node.right)
        
        return calculate_tilt(root)

Complexity

• Time: O(n²) worst case for skewed tree
• Space: O(h) for recursion stack
• Notes: Recalculates subtree sums multiple times, less efficient