> For the complete documentation index, see [llms.txt](https://beesec.gitbook.io/algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://beesec.gitbook.io/algorithms/graphs/binary-search-trees/binary-tree-tilt.md).

# Binary Tree Tilt

{% hint style="info" %}
<https://leetcode.com/problems/binary-tree-tilt/>
{% endhint %}

{% tabs %}
{% tab title="Question" %}
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 child, 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 child.

![](https://853907954-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MKoQiPsXthu7I640wFl%2F-MLd7zjWMXNdK1g-M3lY%2F-MLd9rDmZ1yOkY-x9tXU%2Fimage.png?alt=media\&token=13a7c875-4859-49ec-ba4b-afb0f9695fba)

```
Input: root = [1,2,3]
Output: 1
Explanation: 
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tile of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1
```

{% endtab %}

{% tab title="Answer" %}
This sounds like DFS. So let's start trying to recurse.<br>

Our base case is that if the root is None, we return

```
if not root:
    return 0
```

And then we want to recurse both left and right trees.

```python
        right_sum = self.helper(root.right)
        left_sum = self.helper(root.left)
```

While doing this, we want to sum each side. We can do that by storing them in these variables. And then we calculate the tilt:

```
        tilt = abs(left_sum - right_sum)
        self.total_sum += tilt
```

Finally, when we have reached a leaf node we want it to return the sums of either side added to the current value.&#x20;

```
    return left_sum + right_sum + root.val
```

Thus our solution is:

```python
# 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:
        self.total_sum = 0
        self.helper(root)
        return self.total_sum
    
    def helper(self, root):
        if not root:
            return 0
        right_sum = self.helper(root.right)
        left_sum = self.helper(root.left)
        tilt = abs(left_sum - right_sum)
        self.total_sum += tilt
        
        return left_sum + right_sum + root.val
```

{% endtab %}
{% endtabs %}