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 thesum
of every tree node's tilt.
The tilt of a tree node is the absolute difference between thesum
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 as0
. 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
What do we know?
- We have a binary tree (Most times, it could be empty)
- We need to calculate the tilt of each node in the tree.
- We need to visit every node in the tree.
- 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)
- 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. - We're going to perform a Post Order Traversal
- At each node, we get the
left_sum
andright_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.) - We then calculate the
tilt
of the current node. We do this by calculating the absolute difference between theleft_sum
andright_sum
. This value is then appended to thetilt_counter
. - 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).
- 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;
};
Top comments (1)
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: