Explanation

Given a binary tree, the task is to calculate the tilt of the whole binary 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. To find the tilt of the entire tree, we need to calculate the tilt of each node and then sum them all up.

For example, the tree is

1
2
3   1
4 /   \
52     3

The tilt of node 2 and 3 is 0 because they are leaf nodes and don't have any left or right children. The tilt of node 1 is Absolute_value( 2 - 3) = 1.

So, The tilt of the binary tree is 0 + 0 + 1 = 1.

Approach

The algorithm is a simple recursive approach to traverse the binary tree. It uses an int type variable ans to collect the tilt of each node. In the recursion, first it checks if the current node (root) is null. If it is, the function returns with a value of 0.

Then it calculates the sum of all left child values and the sum of all right child values recursively for the current node. The absolute difference between these two sums will provide the tilt of the existing node which is added to ans.

Lastly, function will return the sum of the current node value and its left and right children values.

Solution

Python

1
2python
3class TreeNode():
4    def __init__(self, val=0, left=None, right=None):
5        self.val = val
6        self.left = left
7        self.right = right
8
9class Solution:
10    def findTilt(self, root: TreeNode) -> int:
11        ans = 0
12        self._sum(root, ans)
13        return ans
14
15    def _sum(self, root: TreeNode, ans: int) -> int:
16        if root is None:
17            return 0
18
19        left = self._sum(root.left, ans)
20        right = self._sum(root.right, ans)
21
22        # calculate tilt of current node and add it to the total tilt
23        ans += abs(left - right)
24
25        return root.val + left + right

Java

1
2java
3class Solution {
4    int tilt = 0;
5    public int findTilt(TreeNode root) {
6        traverse(root);
7        return tilt;
8    }
9
10    public int traverse(TreeNode root) {
11        if (root == null)
12            return 0;
13        
14        // calculate the sum of left and right subtrees
15        int left = traverse(root.left);
16        int right = traverse(root.right);
17
18        tilt += Math.abs(left - right);
19
20        return left + right + root.val;
21    }
22}

JavaScript

1
2javascript
3class Solution {
4    findTilt(root) {
5        this.tilt = 0;
6        this.traverse(root);
7        return this.tilt;
8    }
9
10    traverse(root) {
11        if (root == null)
12            return 0;
13        
14        let left = this.traverse(root.left);
15        let right = this.traverse(root.right);
16
17        this.tilt += Math.abs(left - right);
18
19        return left + right + root.val;
20    }
21}

C++

1
2c++
3class Solution {
4private:
5    int tilts = 0;
6public:
7    int findTilt(TreeNode* root) {
8        postOrder(root);
9        return tilts;
10    }
11
12    int postOrder(TreeNode* root) {
13        if(root == NULL)
14            return 0;
15        
16        int left = postOrder(root->left);
17        int right = postOrder(root->right);
18
19        tilts += abs(left - right);
20
21        return left + right + root->val;
22    }
23};

C#

1
2csharp
3class Solution {
4private int sumTilt = 0;
5
6public int FindTilt(TreeNode root) {
7    tilt(root);
8    return sumTilt;
9}
10
11private int tilt(TreeNode node) {
12    if (node == null)
13        return 0;
14
15    int left = tilt(node.left);
16    int right = tilt(node.right);
17
18    sumTilt += Math.Abs(left - right);
19        
20    return left + right + node.val;
21}
22}

Time Complexity

The approach performs a post-order traversal of the binary tree, i.e., it traverses the left subtree, then the right subtree and finally the root node. Since the whole tree is traversed once, the time complexity for this approach is O(n), where n is the number of nodes.

Space Complexity

The space complexity of this solution is O(h), where h is the height of the tree. The reason is that we use the system stack for recursive function calls, and in the worst-case scenario, if the tree is skewed, we may end up calling the functions recursively for h times (h = height of the tree), hence using up that much space on the system stack.

In conclusion, we can find the tilt of the binary tree using a simple depth-first search approach, where we traverse through the whole tree and calculate the tilt of each node and then sum the tilts up. This task requires knowledge about binary trees and recursion. The time complexity is O(n), and space complexity is O(h) which makes it efficient to use for binary trees of any length and structure. The solutions provided are in popular programming languages including Python, Java, JavaScript, C++, and C#. If you are using some other programming language, the concept remains the same and you can implement it in your respective language without any difficulties. Even though the code may look different due to the syntax of the specific language, they all follow the same logic and concept.