Watch 10 video solutions for Binary Tree Tilt, a easy level problem involving Tree, Depth-First Search, Binary Tree. This walkthrough by Knowledge Center has 4,516 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the root of a binary tree, return the sum of every tree node's tilt.
The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values. If a node does not have a left child, then the sum of the left subtree node values is treated as 0. The rule is similar if the node does not have a right child.
Example 1:
Input: root = [1,2,3] Output: 1 Explanation: Tilt of node 2 : |0-0| = 0 (no children) Tilt of node 3 : |0-0| = 0 (no children) Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3) Sum of every tilt : 0 + 0 + 1 = 1
Example 2:
Input: root = [4,2,9,3,5,null,7] Output: 15 Explanation: Tilt of node 3 : |0-0| = 0 (no children) Tilt of node 5 : |0-0| = 0 (no children) Tilt of node 7 : |0-0| = 0 (no children) Tilt of node 2 : |3-5| = 2 (left subtree is just left child, so sum is 3; right subtree is just right child, so sum is 5) Tilt of node 9 : |0-7| = 7 (no left child, so sum is 0; right subtree is just right child, so sum is 7) Tilt of node 4 : |(3+5+2)-(9+7)| = |10-16| = 6 (left subtree values are 3, 5, and 2, which sums to 10; right subtree values are 9 and 7, which sums to 16) Sum of every tilt : 0 + 0 + 0 + 2 + 7 + 6 = 15
Example 3:
Input: root = [21,7,14,1,1,2,2,3,3] Output: 9
Constraints:
[0, 104].-1000 <= Node.val <= 1000Problem Overview: Each node in a binary tree has a tilt defined as the absolute difference between the sum of values in its left subtree and the sum in its right subtree. The task is to compute the total tilt of the entire tree by summing the tilt of every node.
Approach 1: Pre-computed Subtree Sums (O(n2) time, O(h) space)
A straightforward method computes the sum of each subtree every time you calculate a node's tilt. For every node, run a recursive function that traverses the left subtree to compute its sum and another traversal for the right subtree. The tilt for the node becomes abs(leftSum - rightSum), and you repeat the same logic recursively for all nodes. Because subtree sums are recalculated multiple times, the same nodes are visited repeatedly, which leads to O(n2) time in the worst case (for skewed trees). The recursion stack uses O(h) space, where h is the tree height. This approach is useful for understanding the definition of tilt but is inefficient for large trees.
Approach 2: Post-order Traversal (O(n) time, O(h) space)
The optimal strategy computes subtree sums while traversing the tree once using Depth-First Search. A post-order traversal processes the left subtree, then the right subtree, and finally the current node. When returning from recursion, each call provides the total sum of that subtree. At the current node, compute the tilt with abs(leftSum - rightSum) and add it to a global accumulator. Then return leftSum + rightSum + node.val to the parent call. Each node contributes to the calculation exactly once, producing O(n) time complexity with O(h) recursion space. This method naturally fits tree problems where information flows upward during traversal.
This approach works well for any binary tree because subtree results are reused instead of recomputed. The key insight is combining two tasks in a single DFS pass: computing subtree sums and accumulating tilt.
Recommended for interviews: Interviewers expect the post-order DFS solution. The brute-force subtree-sum approach shows that you understand the tilt definition, but the optimized traversal demonstrates your ability to eliminate repeated work and design linear-time tree algorithms.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pre-computed Subtree Sums | O(nĀ²) | O(h) | Good for understanding the tilt definition or when learning recursion on trees |
| Post-order Traversal (DFS) | O(n) | O(h) | Optimal approach for interviews and production solutions |