Binary Tree Tilt

Question

Given a binary tree, return the tilt of the whole tree.

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 node has tilt 0.

The tilt of the whole tree is defined as the sum of all nodes' tilt.

Example:

Input: 
         1
       /   \
      2     3
Output: 1
Explanation: 
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1

Note:

• The sum of node values in any subtree won't exceed the range of 32-bit integer.
• All the tilt values won't exceed the range of 32-bit integer.

Tags

• Tree

Thought

To solve this problem, there are two subproblems:

1. Calculate the sum of the tree for any root node
2. Traversal for the whole tree to calculate the sum of the tilt

However, if we split the code into two parts and solve them separately, one significant problem comes: efficency. It is obvious that the tree will be traversaled for many times(O(n^2)), and it is very inefficient.

Simple way to solve this is to use the technique called calculating on the fly: we calculate and sum the tilts when calculating the sum of the subtree for each node during the traversal.

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution(object):
    self.result = 0
    def findSum(self, current_root):
        """
        Calculate the sum of the tree whose root is current_root and edit the result by calculating on the fly to avoid unecessary traversal
        """
        if current_root is None:
            return 0
        left_sum = self.findSum(current_root.left)
        right_sum = self.findSum(current_root.right)
        self.result = abs(left_sum - right_sum)
        return current_root.val + left_sum + right_sum

    def findTilt(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.findSum(root)
        return self.result