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.
Examples
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.
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).
- Return Value: The function needs to return the Sum of Tokens (values) in the subtree to the parent.
- Side Effect: While computing the sum, we also calculate the current node's Tilt and add it to a
total_tiltvariable.
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
Visiting Node 4. Waiting for Left and Right subtree sums...
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.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.