563. Binary Tree Tilt 🚀

Solution Developed In:

The Question

For this article we will be covering Leetcode's '563. 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:

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 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
2. Depth First Search
3. Post Order Traversal
4. Recursive Post Order 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 to calculate the tilt of each node.

How we're going to do it:

We're going to use Post Order 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
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, 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.

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.

---

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;
};

Comments

[Samuel Hinchliffe 🚀]

Hey There 👋

---

Thank you for taking the time to look at my solution. I hope you found it interesting and useful.

If you're having difficulties understanding this solution or just need some clarity on a certain section of it. Please do not hesitate to contact me. We're all in this together and I'm happy to help. 😁

---

Contact me here: