Binary TreesProblem 28 of 35
Find Largest subtree sum in a tree
Problem Statement
Given a binary tree, find the largest subtree sum. The subtree sum is the sum of all node values in that subtree (including the root of subtree).
Example:
1
/ \
-2 3
/ \ / \
4 5 -6 2
Subtree sums:
- Subtree rooted at 4: 4
- Subtree rooted at 5: 5
- Subtree rooted at -2: -2 + 4 + 5 = 7
- Subtree rooted at -6: -6
- Subtree rooted at 2: 2
- Subtree rooted at 3: 3 + (-6) + 2 = -1
- Subtree rooted at 1: 1 + 7 + (-1) = 7
Output: 7 (subtree rooted at -2 or entire tree)
Approach 1: Brute Force (Calculate Sum for Each Subtree)
Intuition
For each node, calculate the sum of its subtree. Track the maximum sum seen. This requires recalculating sums repeatedly.
Algorithm
- For each node, calculate the sum of its entire subtree
- Compare with the current maximum
- Recursively process all nodes
- Return the maximum sum found
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int getSubtreeSum(TreeNode root) {
if (root == null) return 0;
return root.val + getSubtreeSum(root.left) + getSubtreeSum(root.right);
}
private void findMaxSum(TreeNode root, int[] maxSum) {
if (root == null) return;
// Calculate sum of current subtree
int currentSum = getSubtreeSum(root);
maxSum[0] = Math.max(maxSum[0], currentSum);
// Check children
findMaxSum(root.left, maxSum);
findMaxSum(root.right, maxSum);
}
public int largestSubtreeSumBruteForce(TreeNode root) {
if (root == null) return 0;
int[] maxSum = {Integer.MIN_VALUE};
findMaxSum(root, maxSum);
return maxSum[0];
}
}Complexity Analysis
- Time Complexity: O(n^2) - For each node, we calculate subtree sum which takes O(n)
- Space Complexity: O(n) - Recursion stack for skewed tree
Approach 2: Optimal (Bottom-Up - Calculate Sum Once)
Intuition
Use postorder traversal (bottom-up). Calculate subtree sum for each node using already computed sums of children. This way, each node is visited only once.
Algorithm
- Perform postorder traversal
- At each node: subtreeSum = node.val + leftSum + rightSum
- Update global maximum with current subtree sum
- Return the subtree sum for parent's use
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int maxSum = Integer.MIN_VALUE;
private int findSubtreeSum(TreeNode root) {
if (root == null) return 0;
// Get sum of left and right subtrees
int leftSum = findSubtreeSum(root.left);
int rightSum = findSubtreeSum(root.right);
// Calculate current subtree sum
int currentSum = root.val + leftSum + rightSum;
// Update maximum
maxSum = Math.max(maxSum, currentSum);
// Return sum for parent's use
return currentSum;
}
public int largestSubtreeSum(TreeNode root) {
if (root == null) return 0;
maxSum = Integer.MIN_VALUE;
findSubtreeSum(root);
return maxSum;
}
}Complexity Analysis
- Time Complexity: O(n) - Each node is visited exactly once
- Space Complexity: O(h) - Recursion stack depth, where h is height of tree
Key Takeaways
- Bottom-up (postorder) is key for single-pass solution
- Return value reuse: Child sum is used by parent - compute once
- Similar to: Maximum path sum, diameter of tree problems
- Global variable pattern: Track maximum while computing something else
- Subtree sum formula: node.val + leftSubtreeSum + rightSubtreeSum