Python 0563.py
class Solution:
def findTilt(self, root: Optional[TreeNode]) -> int:
sum = 0
def tilt(node):
if not node:
return 0
l = tilt(node.left)
r = tilt(node.right)
result = node.val + l + r
node.val = abs(l - r)
nonlocal sum
sum += node.val
return result
tilt(root)
return sum
Difficulty
and has an acceptance rate of about 66% (400k+ submissions).
Typical patterns to solve this problem:
- Binary Tree
- Depth First Search
- Tree
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation defines a class Solution with a method findTilt that computes the total tilt of a binary tree. The tilt of a node is defined as the absolute difference between the sum of values in its left subtree and the sum of values in its right subtree. The method returns the aggregate of all node tilts in the tree. The algorithm performs a single depth-first traversal, updating each node’s value to hold its own tilt while accumulating the overall result in a non-local accumulator.
Core Logic
The method begins by initializing an accumulator named sum to zero. This variable will hold the cumulative tilt of all visited nodes.
sum = 0
A nested helper function tilt is declared to process each node recursively. The helper returns the total sum of values in the subtree rooted at the current node.
def tilt(node):
if not node:
return 0
When the current node is None, the function returns zero, which correctly represents an empty subtree. This base case ensures that leaf nodes are handled without additional conditional checks.
For a non-null node, the helper first recurses on the left child, storing the resulting subtree sum in l.
l = tilt(node.left)
It then recurses on the right child, storing that sum in r.
r = tilt(node.right)
At this point l and r contain the total values of the left and right subtrees respectively. The sum of the entire subtree rooted at the current node is computed by adding the node’s original value to l and r.
result = node.val + l + r
The node’s own tilt is the absolute difference between l and r. The implementation overwrites node.val with this tilt value.
node.val = abs(l - r)
The tilt of the current node is then added to the outer accumulator sum. The nonlocal declaration allows the nested function to modify the variable defined in the enclosing scope.
nonlocal sum
sum += node.val
Finally, the helper returns result, the total sum of the subtree, to be used by its parent call.
return result
After defining the helper, the method invokes it with the root of the tree, thereby triggering the full traversal.
tilt(root)
When the recursion completes, the accumulated sum holds the total tilt of the tree, which is returned as the final answer.
return sum
Edge Cases Handled
The base case if not node: return 0 gracefully handles an empty tree, resulting in a tilt of zero. For a tree consisting of a single node, both left and right subtree sums are zero, so the node’s tilt becomes abs(0 - 0), which is zero, and the accumulator remains unchanged. The recursion naturally accommodates unbalanced trees because each subtree sum is computed independently before the tilt calculation.
Performance Optimizations
The algorithm achieves efficiency by performing a single post-order traversal. By computing the left and right subtree sums before calculating the current node’s tilt, it avoids redundant passes over the same nodes. The use of a non-local accumulator eliminates the need for auxiliary data structures such as lists or dictionaries to store intermediate tilt values. Overwriting node.val with the tilt eliminates the creation of additional variables for temporary storage, reducing memory pressure. The recursion returns only the necessary integer sum for each subtree, keeping the call stack lightweight.
Overall, the implementation delivers a concise and effective solution that leverages recursion, in-place updates, and a shared accumulator to compute the total tilt of a binary tree in a single pass.
ELI5 - Simplified Explanation
Imagine a tree made of numbers where every branch has a value. This code is like a little robot helper designed to visit every single branch to figure out how lopsided the whole thing is. The robot starts at the very top and travels down to the bottom where there is nothing left. When it comes back up, it adds up the values of the branches it just visited to see how heavy each side is. Once the robot knows the weight of the left side and the weight of the right side, it calculates the difference between them. This difference is what is called the tilt. The robot writes this tilt number down, adds it to a big pile of tilt numbers it is keeping for the whole tree, and then tells the next branch how much total weight is hiding underneath it. By the time the robot climbs all the way back to the top of the tree, it has measured every hidden tilt and added them all together to get a final answer.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||||
| www | AlgoMonster | C++ | Python | Java | TS | |||||||
| WalkCCC | C++ | Python | Java | |||||||||
| leetcode.ca | C++ | Python | Java | Go | TS | |||||||
| LeetcodeHelp | C++ | Python | Java | |||||||||
| Progiez | C++ | Python | Java | |||||||||
| github | begeekmyfriend | C | ||||||||||
| BigEggStudy | C# | |||||||||||
| black-shadows | C++ | |||||||||||
| chandansgowda | Python | |||||||||||
| charles-wangkai | Java | |||||||||||
| everthis | JS | |||||||||||
| fartem | Ruby | |||||||||||
| fpdjsns | C++ | |||||||||||
| gouthampradhan | Java | |||||||||||
| halfrost | Go | |||||||||||
| haoel | Python | |||||||||||
| JoshCrozier | JS | |||||||||||
| keineahnung2345 | C++ | |||||||||||
| linouk23 | C++ | |||||||||||
| lkwq007 | Python | |||||||||||
| ruoru | Rust | |||||||||||
| shreymehul | C# | |||||||||||
| suxrobGM | C# | |||||||||||
| trung-hn | Python | |||||||||||
| varunu28 | Java | |||||||||||
| yuanliu666 | Kotlin | |||||||||||
| YuriSpiridonov | Python | |||||||||||
| zfang399 | C++ | |||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||||
| WalkCCC | C++, Python, Java | |||||||||||
| leetcode.ca | C++, Go, Java, Python, TypeScript | |||||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||||
| Progiez | C++, Java, Python | |||||||||||
| begeekmyfriend | C | |||||||||||
| BigEggStudy | C# | |||||||||||
| black-shadows | C++, C++ | |||||||||||
| chandansgowda | Python | |||||||||||
| charles-wangkai | Java | |||||||||||
| everthis | JavaScript | |||||||||||
| fartem | Ruby | |||||||||||
| fpdjsns | C++ | |||||||||||
| gouthampradhan | Java | |||||||||||
| halfrost | Go | |||||||||||
| haoel | Python | |||||||||||
| JoshCrozier | JavaScript | |||||||||||
| keineahnung2345 | C++ | |||||||||||
| linouk23 | C++ | |||||||||||
| lkwq007 | Python | |||||||||||
| ruoru | Rust | |||||||||||
| shreymehul | C# | |||||||||||
| suxrobGM | C# | |||||||||||
| trung-hn | Python | |||||||||||
| varunu28 | Java | |||||||||||
| yuanliu666 | Kotlin | |||||||||||
| YuriSpiridonov | Python | |||||||||||
| zfang399 | C++ |
Videos
Solved On The Same Day
- problem 938: Range Sum of BST
- problem 965: Univalued Binary Tree
- problem 146: LRU Cache
- problem 371: Sum of Two Integers
- problem 865: Smallest Subtree with all the Deepest Nodes
- problem 1201: Ugly Number III
- problem 2707: Extra Characters in a String
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality