Binary Tree Tilt
Problem
Return the sum, over all nodes, of |sum(left subtree) − sum(right subtree)| — the tree's total tilt.
root = [1,2,3]1def find_tilt(root):
total = 0
def s(node):
nonlocal total
if not node: return 0
l, r = s(node.left), s(node.right)
total += abs(l - r)
return node.val + l + r
s(root)
return totalfunction findTilt(root) {
let total = 0;
function s(node) {
if (!node) return 0;
const l = s(node.left), r = s(node.right);
total += Math.abs(l - r);
return node.val + l + r;
}
s(root);
return total;
}class Solution {
int total = 0;
public int findTilt(TreeNode root) { s(root); return total; }
int s(TreeNode n) {
if (n == null) return 0;
int l = s(n.left), r = s(n.right);
total += Math.abs(l - r);
return n.val + l + r;
}
}int total = 0;
int s(TreeNode* n) {
if (!n) return 0;
int l = s(n->left), r = s(n->right);
total += abs(l - r);
return n->val + l + r;
}
int findTilt(TreeNode* root) { total = 0; s(root); return total; }Explanation
A node's tilt is the absolute difference between the sum of its left subtree and the sum of its right subtree. We want to add up the tilt of every node — and the smart move is to compute subtree sums and tilts in the same pass.
The helper s(node) does double duty: it returns the total sum of the subtree rooted at node, while quietly adding that node's tilt to a running total. Because it is post-order, the left and right sums l and r are ready before we need them.
At each node we do total += abs(l - r) for its tilt, then return node.val + l + r upward so the parent can reuse this subtree's sum. A null node returns 0 and contributes nothing.
Example: tree [1, 2, 3]. Leaves 2 and 3 each have tilt 0 and return sums 2 and 3. At root 1, tilt is |2 - 3| = 1, so total = 1, which is the answer.
Each node is visited exactly once, giving O(n) time.