Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Binary Tree Tilt

LeetCode #563Easy
Post-order: return subtree sums, accumulate |L − R|

Given the root of a binary tree, return the sum of every node's tilt, where a node's tilt is the absolute difference between the total value of its left subtree and the total value of its right subtree.

Asked atAmazon
step 1 / 14
binary tree
3
2
5
4
9
7
call stack ↓
(returned)
Post-order DFS (sum up, accumulate tilt)
▸
1total = 0
2sum(node):
3    if node is null: return 0
4    sumL = sum(node.left)
5    sumR = sum(node.right)
6    total += abs(sumL - sumR)         // accumulate tilt
7    return node.val + sumL + sumR     // subtree sum
8// answer = total
state
  • tilt(node)|sumL − sumR|
  • answerΣ tilt(node)
  • total so far0

line 1Tilt of a node = |sum(left subtree) − sum(right subtree)|, and the answer is the sum of every node's tilt. The clean trick: one post-order helper returns each subtree's SUM, and along the way a global accumulator adds in that node's tilt. We compute sums going up, accumulate tilts as a side effect.