Faangprep Logo
LoginRegister
Browse Curriculum
Depth-First Search
Easy

Binary Tree Tilt

Calculate the tilt of the whole tree. The tilt of a node is the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values.
10 min read
Solve on LeetCode
Examples
Input:root = [1,2,3]
Output:1
Explain:

Tilt of node 2: |0-0| = 0. Tilt of node 3: |0-0| = 0. Tilt of node 1: |2-3| = 1. Total = 0 + 0 + 1 = 1.

Input:root = [4,2,9,3,5,null,7]
Output:15
Explain:

Tilt of node 3: 0. Tilt of node 5: 0. Tilt of node 7: 0. Tilt of node 2: |3-5| = 2. Tilt of node 9: |0-7| = 7. Tilt of node 4: |(3+5+2) - (9+7)| = |10 - 16| = 6. Total = 0+0+0+2+7+6 = 15.

Problem Understanding

The Tilt of a tree node is defined as abs(sum(left_subtree) - sum(right_subtree)).
The Total Tilt of the tree is the sum of tilts of all nodes.

We need to traverse the tree, and for every node, compute the sum of its left and right children to find its tilt, while also returning the sum to its parent.

Algorithm Strategy (Post-Order)

We use Post-Order DFS (Bottom-Up).

  1. Return Value: The function needs to return the Sum of Tokens (values) in the subtree to the parent.
  2. Side Effect: While computing the sum, we also calculate the current node's Tilt and add it to a total_tilt variable.

Logic:

  • left_sum = dfs(node.left)
  • right_sum = dfs(node.right)
  • node_tilt = abs(left_sum - right_sum)
  • total_tilt += node_tilt
  • Return node.val + left_sum + right_sum

Interactive Visualization

Step 1 / 1
Empty Heap

Initializing...

1x

Visualize values bubbling up (sums) and tilt being accumulated.

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.