algoadvance

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

The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null nodes have a tilt of 0.

The tilt of the whole tree is the sum of the tilts of all its nodes.

Clarifying Questions

  1. What is the input format?
    • You are given a binary tree represented by its root node.
  2. What should be returned?
    • Return an integer representing the sum of all node tilts in the binary tree.
  3. Are there any constraints on the values within the tree nodes?
    • The number of nodes in the tree is in the range [0, 10^4].
    • -1000 <= Node.val <= 1000

Strategy

To solve this problem, we’ll use a Depth-First Search (DFS) approach, which will allow us to calculate both the sum of the nodes’ values and the tilt in a single pass. We’ll perform the following steps recursively:

  1. Calculate the sum of the subtree rooted at each node: This involves calculating the sum of the left and right subtrees.
  2. Compute the tilt for each node: The tilt of a node is the absolute difference between the sum of the values in the left subtree and the sum of the values in the right subtree.
  3. Accumulate the tilt values: We’ll keep a running total of all tilt values encountered during the DFS.

Code

Here is the Python program that implements the solution:

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

Time Complexity

The time complexity of the above solution is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once.

Space Complexity

The space complexity is O(h), where h is the height of the tree. This is due to the recursion stack space utilization. In the worst case, for a skewed binary tree, h could be equal to n, but for a balanced binary tree, h = log(n).

Try our interview co-pilot at AlgoAdvance.com