Example 1
ready- Input
root = [ 1, 2, 3 ]- Expected
1- Why
- the root contributes |2 - 3| = 1
Binary Tree Tilt
25 min · findTilt()Picture every node as a balance scale. The values hanging below its left and right sides decide how far that scale tips.
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. Given the root of a binary tree, return the sum of every node's tilt.
A few ground rules:
- An empty subtree has sum
0. - A leaf has tilt
0because both of its subtrees are empty. - Negative node values contribute normally to subtree sums.
- An empty tree returns
0.
Constraints
0 <= node count <= 10_000-1_000 <= node.val <= 1_0000 <= total tilt <= 2_147_483_647
Hints
Write the definition first
At one node, compute the complete left-subtree sum and right-subtree sum, take their absolute difference, then repeat for both children.
Spot the repeated work
If every ancestor asks for a descendant's subtree sum again, a long one-sided tree gets scanned over and over. What result could each child hand to its parent?
One return value, one side effect
A post-order traversal handles both children before their parent, so a node can
receive both child sums. Add their difference to a running total, then return
node.val + left_sum + right_sum upward.
Follow-up
Could you produce every node's individual tilt as well as the total in the same pass?
Visible cases
Examples
Example 2
ready- Input
root = [ 4, 2, 9, 3, 5, null, 7 ]- Expected
15- Why
- adding every node's local imbalance gives 15
Example 3
ready- Input
root = [ 1 ]- Expected
0- Why
- a leaf has two empty subtrees
Interview signal
Asked at
AmazonGoogle
The number you need at a parent — a child's complete subtree sum — becomes available only after that child has been fully processed.
Repeated subtree sums
Translate the definition directly. At every node, walk its left subtree to total it, walk its right subtree to total it, add the difference, then solve both child trees.
import sys
sys.setrecursionlimit(20_000)
def find_tilt(root: TreeNode | None) -> int:
def subtree_sum(node: TreeNode | None) -> int:
if node is None:
return 0
return node.val + subtree_sum(node.left) + subtree_sum(node.right)
def total_tilt(node: TreeNode | None) -> int:
if node is None:
return 0
own_tilt = abs(subtree_sum(node.left) - subtree_sum(node.right))
return own_tilt + total_tilt(node.left) + total_tilt(node.right)
return total_tilt(root)Time O(n²) in the worst case — a skewed tree makes subtree_sum revisit the same
suffix for many ancestors. Space O(h) for recursive calls.
One post-order pass
Post-order traversal processes both children before their parent. Store each finished subtree's sum. When the parent comes off the stack, both numbers needed for its tilt are ready, and its own sum can be stored for the next level.
def find_tilt(root: TreeNode | None) -> int:
if root is None:
return 0
subtree_sums: dict[TreeNode, int] = {}
stack = [(root, False)]
total = 0
while stack:
node, expanded = stack.pop()
if expanded:
left_sum = subtree_sums.get(node.left, 0)
right_sum = subtree_sums.get(node.right, 0)
total += abs(left_sum - right_sum)
subtree_sums[node] = node.val + left_sum + right_sum
continue
stack.append((node, True))
if node.right is not None:
stack.append((node.right, False))
if node.left is not None:
stack.append((node.left, False))
return totalEach subtree sum is calculated once, at the exact moment both of its child sums are
known. Negative values need no special branch; subtraction and abs already express the
definition.
Time O(n) — two stack events per node. Space O(n) for the explicit stack and the stored subtree sums.
A recursive post-order solution can use O(h) auxiliary space, but Python's default recursion limit can't cover a 10,000-node line. The explicit stack remains safe there.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
1
Run: visible + custom · Submit: full suite