Binary Tree Tilt
EasyPrompt
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 = 1Example 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 = 15Example 3:
Input: root = [21,7,14,1,1,2,2,3,3]
Output: 9
Constraints:
- The number of nodes in the tree is in the range
[0, 104]. -1000 <= Node.val <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves traversing the tree and, for each node, separately calculating the sum of its left and right subtrees to find its tilt. This leads to redundant calculations as subtree sums are computed multiple times.
Algorithm
- Initialize a global variable
totalTiltto 0. - Create a main traversal function
traverse(node). - If
nodeis null, return. - Inside
traverse(node):- Calculate the sum of the left subtree by calling a helper function
getSum(node.left). - Calculate the sum of the right subtree by calling
getSum(node.right). - Calculate the node's tilt:
tilt = Math.abs(leftSum - rightSum). - Add the tilt to
totalTilt. - Recursively call
traverse(node.left)andtraverse(node.right).
- Calculate the sum of the left subtree by calling a helper function
- The
getSum(node)helper function:- If
nodeis null, return 0. - Return
node.val + getSum(node.left) + getSum(node.right).
- If
- Start the process by calling
traverse(root). - Return
totalTilt.
Walkthrough
We can define a main traversal function that visits every node in the tree (e.g., using preorder traversal). For each node visited, we calculate its tilt. To do this, we need the sum of all node values in its left subtree and its right subtree. We create a helper function, getSum(node), which recursively calculates the sum of all nodes in the subtree rooted at node. In the main traversal, for a node curr, we compute leftSum = getSum(curr.left) and rightSum = getSum(curr.right). The tilt for curr is abs(leftSum - rightSum). We accumulate these tilts in a total sum variable. The main traversal then continues to the children of curr. The main drawback is that the getSum function traverses subtrees that are visited repeatedly by the main traversal function for ancestor nodes, leading to significant inefficiency.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { private int totalTilt = 0; public int findTilt(TreeNode root) { traverse(root); return totalTilt; } // Main traversal to visit each node private void traverse(TreeNode node) { if (node == null) { return; } // Calculate tilt for the current node int leftSum = getSum(node.left); int rightSum = getSum(node.right); totalTilt += Math.abs(leftSum - rightSum); // Continue traversal traverse(node.left); traverse(node.right); } // Helper function to calculate the sum of a subtree private int getSum(TreeNode node) { if (node == null) { return 0; } return node.val + getSum(node.left) + getSum(node.right); }}Complexity
Time
O(N^2) in the worst case (for a skewed tree) and O(N log N) for a balanced tree, where N is the number of nodes. For each of the N nodes, we might traverse its entire subtree to calculate the sum.
Space
O(N) in the worst case for the recursion stack depth. This occurs in a skewed tree, where N is the number of nodes.
Trade-offs
Pros
Simple to understand and implement as it directly follows the problem definition.
Separates the logic of traversal and sum calculation.
Cons
Highly inefficient due to redundant computations. The sum of each subtree is calculated multiple times.
Poor time complexity, especially for deep or skewed trees.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans ; public int findTilt ( TreeNode root ) { ans = 0 ; sum ( root ); return ans ; } private int sum ( TreeNode root ) { if ( root == null ) { return 0 ; } int left = sum ( root . left ); int right = sum ( root . right ); ans += Math . abs ( left - right ); return root . val + left + right ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.