563. Binary Tree Tilt 🚀
Tags: javascript, beginners, tutorial, leetcode
Published: 2022-05-08 20:19:33

### Solution Developed In:
![JavaScript](https://img.shields.io/badge/javascript-%23323330.svg?style=for-the-badge&logo=javascript&logoColor=%23F7DF1E)

## The Question
For this article we will be covering Leetcode's '[563. Binary Tree Tilt](https://leetcode.com/problems/binary-tree-tilt/)' question. 

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 the node does not have a right child.

Example:

>![Example](https://assets.leetcode.com/uploads/2020/10/20/tilt1.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
```

## Explaining The Question
This Question is rated **Easy**. Which I believe is ***completely in-accurate and misleading***. 

I believe that this question can only be considered easy is if you understand the ***Medium level concepts***. Like how to sum a binary tree, how to traverse a binary tree, and how to traverse a binary tree recursively. What [Post Order Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/) is and how we can use it to calculate tree sums. If you understand the **medium** level concepts, then you can easily understand this question, but the question itself is not for people who don't know these concepts.

What we're being asked is to calculate the difference between every node's left and right subtree sums. Which translates to:
At every node we visit, get the sum of the left trees and right trees. Figure out the difference between the two. Then we can add that difference to the total sum. We repeat this process for every node in the entire tree.

##  Recommended Knowledge
1. [Binary Tree](https://en.wikipedia.org/wiki/Binary_tree)
2. [Depth First Search](https://en.wikipedia.org/wiki/Depth-first_search)
3. [Post Order Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/) 
4. [Recursive Post Order Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)

## What do we know?
1. We have a ***binary tree*** (Most times, it could be empty)
2. We need to calculate the **tilt** of each node in the tree.
3. We need to visit every **node** in the tree.
4. We're going to need to use [Post Order Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/) to calculate the **tilt** of each node.

## How we're going to do it:

We're going to use [Post Order Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/) to calculate the **tilt** of each node. We do this by calculating the sum of the left and right subtrees. Given the sum of the left and right subtrees, we can calculate the **tilt** of the current node.

The tilt is calculated by: 
```
tilt = abs(left_subtree_sum - right_subtree_sum)
```

1. We're going to declare a `tilt_counter` that will be used to store the total tilt of all nodes in the tree. Lots of (`+=`) operations. 
2. We're going to perform a [Post Order Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/) 
3. At each node, we get the `left_sum` and `right_sum` of the current node. Which represents the sum of the left and right subtrees. (Don't worry if this makes no sense, it will soon be explained.)
4. We then calculate the `tilt` of the current node. We do this by calculating the absolute difference between the `left_sum` and `right_sum`. This value is then appended to the `tilt_counter`.
5. We then return the sum of the current node. The sum of a current node is calculated by (left_sum + right_sum + current node sum).
6. After calculating that, we return that value. Because we're using [Post Order Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/), we can return the sum of the current node to it's parent node within the tree. This is how we get the sub tree sums at point 3. 


## Big O Notation:
* Time Complexity:   *O(**n**)* | Where ***n*** is the number of nodes in our ***Binary Tree*** | As we're going to traverse all of the nodes within the tree.
  
* Space Complexity: *O(**h**)* | Where ***h*** is the height of our ***Binary Tree*** | As we're going to store the height of the tree within the internal [call stack](https://en.wikipedia.org/wiki/Call_stack).


## Leetcode Results:

See Submission Link: 

* Runtime: 79 ms, faster than ***80.75%*** of JavaScript online submissions for Binary Tree Tilt.
* Memory Usage: 47 MB, less than ***85.45%*** of JavaScript online submissions for Binary Tree Tilt.

[![LeetCode](https://img.shields.io/badge/LeetCode-000000?style=for-the-badge&logo=LeetCode&logoColor=#d16c06)](https://leetcode.com/submissions/detail/695684669/)


***

# The Solution
```
var findTilt = function (root) {

    /* -------------------------------------------------------------------------- */
    /*                            563. Binary Tree Tilt                           */
    /* -------------------------------------------------------------------------- */

    /**
     * @author  Samuel Hinchliffe
     * @see    {@link linkedin.com/in/samuel-hinchliffe-🚀-2bb5801a5/ | Author's Linkedin }
     * @see    {@link github.com/Samuel-Hinchliffe}
     */

    // Our tilt counter (Keeps track of the diff between the left and right subtrees)
    let tilt_counter = 0;

    // Recursive function to traverse the tree
    // In a post order fashion, get all the sums for all the subtrees
    // we then figure out the difference between the left and right subtrees
    // and add that to the tilt counter. 
    const post_order_traversal = (node) => {

        // If the node does not exist.
        // It has no value and therefore it's a 0.
        if (!node) {
            return 0;
        }

        // Post Order, get me their SUMS!!!
        let left_sum  = post_order_traversal(node.left);
        let right_sum = post_order_traversal(node.right);

        // Figure out the difference between the left and right subtrees
        // We use the absolute value of the difference to keep track of the tilt
        tilt_counter += Math.abs(left_sum - right_sum);

        // Return the value of the node and it's subtrees.
        return left_sum + right_sum + node.val;
    };

    post_order_traversal(root);
    return tilt_counter;
};

```