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.
The idea behind the post-order traversal approach is to calculate the tilt of a node when all its children have been processed. For each node, compute the sum of node values for the left and right subtrees separately, calculate the node's tilt as the absolute difference of these two sums, and then propagate these subtree sums up to the parent node.
The C solution uses a helper function findTiltUtil which computes the sum of subtree node values and the tilt. It takes a pointer to tiltSum which accumulates the total tilt as a side effect.
Time Complexity: O(n) where n is the number of nodes, as we visit each node once. Space Complexity: O(h) where h is the height of the tree, due to the recursion stack.
In this approach, we preprocess the subtree sums for each node iteratively or recursively. Then we use these sums to calculate the tilt for each node in a separate pass through the tree. This separation of concerns can offer cleaner logic and easier maintenance of code.
In this C solution, an initial two-pass approach is refined to a more efficient calculation of both the subtree sums and the tilt within two separate but integrated recursions. This eliminates redundant recalculations.
Time Complexity: O(n^2) because calculateSubtreeSum might be called multiple times. Space Complexity: O(h).
We design a function dfs to calculate the sum of nodes in the subtree rooted at the current node. In the dfs function, we first check if the current node is null. If it is, we return 0. Then we recursively call the dfs function to calculate the sum of nodes in the left subtree l and the sum of nodes in the right subtree r. Next, we calculate the tilt of the current node, which is |l - r|, and add it to the answer. Finally, we return the sum of nodes of the current node, which is l + r + root.val.
In the main function, we initialize the answer to 0, then call the dfs function to calculate the tilt of the entire tree and return the answer.
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Post-order Traversal | Time Complexity: O(n) where n is the number of nodes, as we visit each node once. Space Complexity: O(h) where h is the height of the tree, due to the recursion stack. |
| Pre-computed Subtree Sums | Time Complexity: O(n^2) because calculateSubtreeSum might be called multiple times. Space Complexity: O(h). |
| Recursion | — |
| 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 |
Binary tree Tilt | LeetCode 563 | C++, Java, Python • Knowledge Center • 4,516 views views
Watch 9 more video solutions →Practice Binary Tree Tilt with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor