Binary TreesProblem 26 of 35
Sum of Nodes on the Longest path from root to leaf node
Problem Statement
Given a binary tree, find the sum of all nodes on the longest path from root to any leaf node. If two or more paths have the same length, return the one with the maximum sum.
Example:
4
/ \
2 5
/ \ \
7 1 2
/ \
6 3
/
8
Longest paths (length 5):
- 4 → 2 → 1 → 6 (length 4, sum = 13)
- 4 → 5 → 2 → 3 → 8 (length 5, sum = 22)
Output: 22
Approach 1: Brute Force (Find All Root-to-Leaf Paths)
Intuition
Generate all root-to-leaf paths, store their lengths and sums. Find the maximum length, then among all paths with that length, find the maximum sum.
Algorithm
- Generate all root-to-leaf paths using DFS
- Store each path's length and sum
- Find the maximum length
- Among paths with max length, find maximum sum
- Return that sum
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void findAllPaths(TreeNode root, int length, int sum,
List<int[]> paths) {
if (root == null) return;
length++;
sum += root.val;
// If leaf node, store the path info
if (root.left == null && root.right == null) {
paths.add(new int[]{length, sum});
return;
}
// Traverse children
findAllPaths(root.left, length, sum, paths);
findAllPaths(root.right, length, sum, paths);
}
public int sumOfLongestPathBruteForce(TreeNode root) {
if (root == null) return 0;
List<int[]> paths = new ArrayList<>(); // {length, sum}
findAllPaths(root, 0, 0, paths);
// Find maximum length
int maxLength = 0;
for (int[] p : paths) {
maxLength = Math.max(maxLength, p[0]);
}
// Find maximum sum among paths with max length
int maxSum = Integer.MIN_VALUE;
for (int[] p : paths) {
if (p[0] == maxLength) {
maxSum = Math.max(maxSum, p[1]);
}
}
return maxSum;
}
}Complexity Analysis
- Time Complexity: O(n^2) - O(n) paths, each path can have O(n) nodes
- Space Complexity: O(n) - Storing all paths
Approach 2: Optimal (Single Pass with Global Variables)
Intuition
Track the maximum length and corresponding maximum sum while traversing. For each leaf, update global variables if current path is longer, or if same length with greater sum.
Algorithm
- Use global variables for max length and max sum
- DFS traversal tracking current length and sum
- At each leaf, compare with global values
- If longer path found, update both length and sum
- If same length with greater sum, update sum
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int maxLength = 0;
private int maxSum = 0;
private void dfs(TreeNode root, int length, int sum) {
if (root == null) return;
length++;
sum += root.val;
// If leaf node, check if this path is better
if (root.left == null && root.right == null) {
if (length > maxLength) {
maxLength = length;
maxSum = sum;
} else if (length == maxLength && sum > maxSum) {
maxSum = sum;
}
return;
}
// Traverse children
dfs(root.left, length, sum);
dfs(root.right, length, sum);
}
public int sumOfLongestPath(TreeNode root) {
if (root == null) return 0;
maxLength = 0;
maxSum = 0;
dfs(root, 0, 0);
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
- Two criteria: First maximize length, then maximize sum among same lengths
- Single pass possible by tracking global maximum values
- Update strategy: Update sum when length is greater OR when length equals and sum is greater
- Path tracking from root to leaf requires carrying state through recursion
- Similar problems: Longest path in tree, maximum sum path from root to leaf