Binary Tree Tilt — Solution in Python, Java & C++
Binary Tree Tilt solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Binary Tree Tilt is an easy coding problem on depth-first search and trees, asked in Amazon and Meta interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return the sum of the tilts of all its nodes.
The tilt of a node is the absolute difference between the sum of all values in its left subtree and the sum of all values in its right subtree. A missing subtree has sum 0, so a leaf has tilt 0.
Example 1
Input: root = [1,2,3]
Output: 1
Explanation: The leaves 2 and 3 have tilt 0; the root has tilt |2 - 3| = 1.
Example 2
Input: root = [4,2,9,3,5,null,7]
Output: 15
Explanation: Tilts: 3, 5 and 7 are leaves (0); 2 → |3 - 5| = 2; 9 → |0 - 7| = 7; 4 → |(2+3+5) - (9+7)| = 6. Total 2 + 7 + 6 = 15.
Example 3
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, 1000] (LeetCode allows 10^4; lowered here so the total tilt provably fits in a 32-bit integer)-1000 <= Node.val <= 1000
Hints for Binary Tree Tilt
Hint 1
A node's tilt needs the sums of its two subtrees — information that flows up from the children.
Hint 2
Recomputing a subtree's sum for every ancestor costs O(n^2) on a chain.
Hint 3
Let one post-order helper return its subtree's sum while adding
|leftSum - rightSum|to a running total.
How to solve Binary Tree Tilt
Subtree sums combine bottom-up: sum(node) = node.val + sum(left) + sum(right). A post-order walk that returns each subtree's sum has both children's sums in hand at every node — exactly what its tilt needs.
Approach
- Define
sum(null) = 0. - At a node, compute
l = sum(left)andr = sum(right). - Add
|l - r|to the running total. - Return
node.val + l + r. - Call
sum(root)and return the total.
Why it works
Each node's tilt is added exactly once — when its own call has both subtree sums — and each subtree sum is computed exactly once, by the call at that subtree's root, so the walk is linear.
Complexity
- Time —
O(n) - Space —
O(h) recursion depth
Pitfalls
- The tilt uses the sums of whole subtrees, not just the two children's values.
- Return the subtree sum from the helper, not the tilt — the parent needs the sum.
- An empty tree has total tilt 0.
Reference solution
Python
from typing import Optional
def findTilt(root: Optional[TreeNode]) -> int:
total = 0
def subtree_sum(node):
nonlocal total
if node is None:
return 0
l = subtree_sum(node.left)
r = subtree_sum(node.right)
total += abs(l - r)
return node.val + l + r
subtree_sum(root)
return totalJava
public static int findTilt(TreeNode root) {
int[] total = new int[1];
tiltSum(root, total);
return total[0];
}
static int tiltSum(TreeNode node, int[] total) {
if (node == null) return 0;
int l = tiltSum(node.left, total);
int r = tiltSum(node.right, total);
total[0] += Math.abs(l - r);
return node.val + l + r;
}C++
int tiltSum(TreeNode* node, int& total) {
if (!node) return 0;
int l = tiltSum(node->left, total);
int r = tiltSum(node->right, total);
total += abs(l - r);
return node->val + l + r;
}
int findTilt(TreeNode* root) {
int total = 0;
tiltSum(root, total);
return total;
}JavaScript
var findTilt = function(root) {
var total = { value: 0 };
tiltSum(root, total);
return total.value;
};
var tiltSum = function(node, total) {
if (node === null) return 0;
var l = tiltSum(node.left, total);
var r = tiltSum(node.right, total);
total.value += Math.abs(l - r);
return node.val + l + r;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals