# Binary Tree Tilt
**Difficulty:** EASY
[External](https://leetcode.com/problems/binary-tree-tilt)
Canonical: https://scaleengineer.com/dsa/problems/binary-tree-tilt
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Indeed](https://scaleengineer.com/companies/indeed)
---
## Problem
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 the node does not have a right child.

**Example 1:**

![](https://assets.glich.co/dsa/binary-tree-tilt/image0.jpg) 

**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)
Tilt 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

**Example 2:**

![](https://assets.glich.co/dsa/binary-tree-tilt/image1.jpg) 

**Input:** root = [4,2,9,3,5,null,7]
**Output:** 15
**Explanation:** 
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 5 : |0-0| = 0 (no children)
Tilt of node 7 : |0-0| = 0 (no children)
Tilt of node 2 : |3-5| = 2 (left subtree is just left child, so sum is 3; right subtree is just right child, so sum is 5)
Tilt of node 9 : |0-7| = 7 (no left child, so sum is 0; right subtree is just right child, so sum is 7)
Tilt of node 4 : |(3+5+2)-(9+7)| = |10-16| = 6 (left subtree values are 3, 5, and 2, which sums to 10; right subtree values are 9 and 7, which sums to 16)
Sum of every tilt : 0 + 0 + 0 + 2 + 7 + 6 = 15

**Example 3:**

![](https://assets.glich.co/dsa/binary-tree-tilt/image2.jpg) 

**Input:** root = [21,7,14,1,1,2,2,3,3]
**Output:** 9

**Constraints:**

* The number of nodes in the tree is in the range `[0, 104]`.
* `-1000 <= Node.val <= 1000`

# Approaches
## Brute Force with Redundant Sum Calculation
This approach involves traversing the tree and, for each node, separately calculating the sum of its left and right subtrees to find its tilt. This leads to redundant calculations as subtree sums are computed multiple times.
**Time:** O(N^2) in the worst case (for a skewed tree) and O(N log N) for a balanced tree, where N is the number of nodes. For each of the N nodes, we might traverse its entire subtree to calculate the sum. · **Space:** O(N) in the worst case for the recursion stack depth. This occurs in a skewed tree, where N is the number of nodes.
**Pros:** Simple to understand and implement as it directly follows the problem definition.; Separates the logic of traversal and sum calculation.
**Cons:** Highly inefficient due to redundant computations. The sum of each subtree is calculated multiple times.; Poor time complexity, especially for deep or skewed trees.
### Explanation
We can define a main traversal function that visits every node in the tree (e.g., using preorder traversal). For each node visited, we calculate its tilt. To do this, we need the sum of all node values in its left subtree and its right subtree. We create a helper function, `getSum(node)`, which recursively calculates the sum of all nodes in the subtree rooted at `node`. In the main traversal, for a node `curr`, we compute `leftSum = getSum(curr.left)` and `rightSum = getSum(curr.right)`. The tilt for `curr` is `abs(leftSum - rightSum)`. We accumulate these tilts in a total sum variable. The main traversal then continues to the children of `curr`. The main drawback is that the `getSum` function traverses subtrees that are visited repeatedly by the main traversal function for ancestor nodes, leading to significant inefficiency.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int totalTilt = 0;

    public int findTilt(TreeNode root) {
        traverse(root);
        return totalTilt;
    }

    // Main traversal to visit each node
    private void traverse(TreeNode node) {
        if (node == null) {
            return;
        }
        // Calculate tilt for the current node
        int leftSum = getSum(node.left);
        int rightSum = getSum(node.right);
        totalTilt += Math.abs(leftSum - rightSum);

        // Continue traversal
        traverse(node.left);
        traverse(node.right);
    }

    // Helper function to calculate the sum of a subtree
    private int getSum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return node.val + getSum(node.left) + getSum(node.right);
    }
}
```
### Algorithm
- Initialize a global variable `totalTilt` to 0.
- Create a main traversal function `traverse(node)`.
- If `node` is null, return.
- Inside `traverse(node)`:
    - Calculate the sum of the left subtree by calling a helper function `getSum(node.left)`.
    - Calculate the sum of the right subtree by calling `getSum(node.right)`.
    - Calculate the node's tilt: `tilt = Math.abs(leftSum - rightSum)`.
    - Add the tilt to `totalTilt`.
    - Recursively call `traverse(node.left)` and `traverse(node.right)`.
- The `getSum(node)` helper function:
    - If `node` is null, return 0.
    - Return `node.val + getSum(node.left) + getSum(node.right)`.
- Start the process by calling `traverse(root)`.
- Return `totalTilt`.

## Optimized Single-Pass Post-order Traversal
This efficient approach uses a single post-order traversal to solve the problem. By processing child nodes before their parent, we can calculate a node's tilt and simultaneously compute the sum of its subtree to pass up to its parent. This avoids redundant calculations.
**Time:** O(N), where N is the number of nodes in the tree. This is because we visit each node exactly once. · **Space:** O(H), where H is the height of the tree, due to the recursion stack. In the worst case of a skewed tree, this becomes O(N). In the best case of a balanced tree, it's O(log N).
**Pros:** Highly efficient with linear time complexity as each node is visited only once.; Elegant solution that combines sum calculation and tilt calculation in a single traversal.; Optimal in terms of time complexity.
**Cons:** The recursive function has a dual responsibility (calculating sum and updating tilt), which might be slightly less intuitive than separating concerns.; Uses a member variable or a global variable to accumulate the tilt, which can be considered a side effect.
### Explanation
The key insight is that to calculate a node's tilt, we need the sum of its left and right subtrees. After calculating the tilt, the node's parent needs the sum of the entire subtree rooted at the current node. Both can be done in one go. We use a recursive helper function that performs a post-order traversal. Let's call it `valueSum(node)`. This function will have two responsibilities: 1. Return the sum of the subtree rooted at `node`. 2. Update a global or member variable with the tilt of `node`. The `valueSum(node)` function works as follows: - Base Case: If `node` is null, it represents an empty subtree, so it returns a sum of 0. - Recursive Step: It recursively calls itself for the left and right children: `leftSum = valueSum(node.left)` and `rightSum = valueSum(node.right)`. - Process Node: With `leftSum` and `rightSum` available, it calculates the tilt for the current node: `tilt = Math.abs(leftSum - rightSum)`. This tilt is added to a running total. - Return Value: The function returns the total sum of the subtree rooted at `node`, which is `node.val + leftSum + rightSum`. This value is then used by the node's parent. The main function initializes the total tilt to zero, calls the helper function on the root, and then returns the accumulated total tilt.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int totalTilt = 0;

    public int findTilt(TreeNode root) {
        valueSum(root);
        return totalTilt;
    }

    /**
     * Performs a post-order traversal.
     * Calculates the tilt for the current node and adds it to the total.
     * Returns the sum of the subtree rooted at the current node.
     */
    private int valueSum(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // Recursively find the sum of left and right subtrees
        int leftSum = valueSum(node.left);
        int rightSum = valueSum(node.right);

        // Calculate the tilt for the current node and add to the total
        int tilt = Math.abs(leftSum - rightSum);
        this.totalTilt += tilt;

        // Return the sum of the current subtree to the parent
        return node.val + leftSum + rightSum;
    }
}
```
### Algorithm
- Initialize a global variable `totalTilt` to 0.
- Define a recursive helper function `valueSum(node)` that returns an integer (the sum of the subtree).
- Base Case for `valueSum(node)`: If `node` is null, return 0.
- Recursive Step:
    - Call `valueSum` on the left child to get the sum of the left subtree: `leftSum = valueSum(node.left)`.
    - Call `valueSum` on the right child to get the sum of the right subtree: `rightSum = valueSum(node.right)`.
- Process the current node:
    - Calculate the tilt: `tilt = Math.abs(leftSum - rightSum)`.
    - Add this tilt to the `totalTilt`: `totalTilt += tilt`.
- Return the sum of the current subtree: `node.val + leftSum + rightSum`.
- In the main function, call `valueSum(root)`.
- Return the final `totalTilt`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans ; public int findTilt ( TreeNode root ) { ans = 0 ; sum ( root ); return ans ; } private int sum ( TreeNode root ) { if ( root == null ) { return 0 ; } int left = sum ( root . left ); int right = sum ( root . right ); ans += Math . abs ( left - right ); return root . val + left + right ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int ans ; int findTilt ( TreeNode * root ) { ans = 0 ; sum ( root ); return ans ; } int sum ( TreeNode * root ) { if ( ! root ) return 0 ; int left = sum ( root -> left ), right = sum ( root -> right ); ans += abs ( left - right ); return root -> val + left + right ; } };
```

### Python

```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 : ans = 0 def sum ( root ): if root is None : return 0 nonlocal ans left = sum ( root . left ) right = sum ( root . right ) ans += abs ( left - right ) return root . val + left + right sum ( root ) return ans
```