Binary Tree Tilt

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

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: 
         1
       /   \
      2     3
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


Input：
{1,1,#,2,3}
Output：
7

Explanation：
        1
      /
    1
   /  \
2     3

Analyzation

Recursion

This problem is all about the relationship between the sum of a tree and the tilt of the tree. The sum is based on the tilt value and the tilt value will be used for the next sum.

Therefore, there should be two outputs which are sum and tilt and that should be divided to left and right. The returned sum should be root.val + leftsum + rightsum, and the returned tilt should be left tilt + right tilt + tilt.

The Code

class Solution:
    """
    @param root: the root
    @return: the tilt of the whole tree
    """
    def findTilt(self, root):
        # Write your code here
        return self.dfs(root)[1]
    
    def dfs(self, root):
        if root is None:
            return 0, 0
        
        # sum is based on tilt values, tilt value is based on sum values, so both values should be kept
        left_sum, left_tilt = self.dfs(root.left)
        right_sum, right_tilt = self.dfs(root.right)
        
        tilt = abs(left_sum - right_sum)
            
        return root.val + left_sum + right_sum, left_tilt + right_tilt + tilt

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).