Binary Tree Tilt - Leetcode Solution

Problem statement:

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 subtree, 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 subtree.

Solution:

To solve this problem, we can use recursion. We first define a recursive function called "tilt_helper" that takes a TreeNode as input and returns a tuple consisting of the sum of all values in the subtree rooted at that node and the total tilt of that node.

def tilt_helper(root): if root is None: return (0,0) left_sum, left_tilt = tilt_helper(root.left) right_sum, right_tilt = tilt_helper(root.right) root_sum = root.val + left_sum + right_sum root_tilt = abs(left_sum - right_sum) + left_tilt + right_tilt return (root_sum, root_tilt)

The function first checks whether the node is None. If it is, the function returns a tuple (0,0). Otherwise, the function calls itself recursively on the left and right subtrees and unpacks the returned tuples into the left_sum, left_tilt, right_sum, and right_tilt variables.

The total sum of the subtree rooted at this node is calculated as the sum of the value of this node and the sums of the left and right subtrees. The total tilt of this node is calculated as the absolute difference between the sum of the left subtree and right subtree, plus the tilts of the left and right subtrees.

Finally, the function returns a tuple consisting of the total sum and total tilt for this node.

To get the final result, we can simply call tilt_helper() function with the root of the given binary tree as input and extract the second value from the returned tuple.

def findTilt(root): return tilt_helper(root)[1]

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. This is because the function visits each node exactly once. The space complexity of this solution is also O(n) since the function call stack could contain up to n nodes if the binary tree is skewed.

1