Binary Tree Path Sum - Maximum Sum Leaf to Root path

Problem

Find the maximum sum leaf-to-root path in a Binary Tree. This means that among all the paths from leaves to the root, find the path which has the maximum sum.

Examples

Example 1

graph TD
    A[10]
    A --> B[8]
    A --> C[2]
    B --> D[3]
    B --> E[5]
    C --> F[2]
    C --> G[1]
    
    classDef maxPath fill:#f9f,stroke:#333,stroke-width:2px;
    A:::maxPath
    B:::maxPath
    E:::maxPath

Input: [10, 8, 2, 3, 5, 2, 1]
Output: [5, 8, 10]
Explanation: The maximum sum path from leaf to root is 5 -> 8 -> 10 which has a sum of 23.

Example 2

graph TD
    A[-10]
    A --> B[20]
    A --> C[30]
    B --> D[-10]
    B --> E[50]
    C --> F[35]
    C --> G[100]
    
    classDef maxPath fill:#f9f,stroke:#333,stroke-width:2px;
    A:::maxPath
    C:::maxPath
    G:::maxPath

Input: [-10, 20, 30, -10, 50, 35, 100]
Output: [100, 30,-10]
Explanation: The maximum sum path from leaf to root is 100-> 30 -> -10 which has a sum of 120.

Solution

Method 1 - DFS

To find the maximum sum leaf-to-root path in a binary tree, we need to explore all paths from leaves to the root. This involves traversing the tree and at each node, keeping track of the maximum sum path rooted at that node.

Here is the approach:

1. Tree Traversal: Use Depth First Search (DFS) to explore all possible paths from leaves to the root.
2. Track Maximum Sum: For each path, calculate the sum and update the maximum sum if the current path's sum exceeds the previously recorded maximum sum.
3. Store Path: As we traverse, keep track of nodes in the current path and update the path if the current path's sum is greater.

Code

Java

class Solution {
    public List<Integer> maxSumLeafToRoot(TreeNode root) {
        if (root == null) return new ArrayList<>();
        
        List<Integer> maxPath = new ArrayList<>();
        List<Integer> currentPath = new ArrayList<>();
        int[] maxSum = {Integer.MIN_VALUE};
        
        dfs(root, 0, maxSum, maxPath, currentPath);
        Collections.reverse(maxPath); // Reverse to get the path from leaf to root
        return maxPath;
    }
    
    private void dfs(TreeNode node, int currentSum, int[] maxSum, List<Integer> maxPath, List<Integer> currentPath) {
        if (node == null) return;
        
        currentSum += node.val;
        currentPath.add(node.val);
        
        // If it's a leaf node
        if (node.left == null && node.right == null) {
            if (currentSum > maxSum[0]) {
                maxSum[0] = currentSum;
                maxPath.clear();
                maxPath.addAll(currentPath);
            }
        } else {
            dfs(node.left, currentSum, maxSum, maxPath, currentPath);
            dfs(node.right, currentSum, maxSum, maxPath, currentPath);
        }
        
        // Backtrack
        currentPath.remove(currentPath.size() - 1);
    }
}

Python

class Solution:
    def maxSumLeafToRoot(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        self.max_sum = float('-inf')
        self.max_path = []

        current_path = []
        self.dfs(root, 0, current_path)
        return self.max_path[::-1] # Reverse the path for leaf-to-root order

    def dfs(self, node: Optional[TreeNode], current_sum: int, current_path: List[int]) -> None:
        if not node:
            return

        current_sum += node.val
        current_path.append(node.val)

        # If it's a leaf node
        if not node.left and not node.right:
            if current_sum > self.max_sum:
                self.max_sum = current_sum
                self.max_path = list(current_path)
        else:
            self.dfs(node.left, current_sum, current_path)
            self.dfs(node.right, current_sum, current_path)

        current_path.pop()  # Backtrack

Complexity

• ⏰ Time complexity: O(n) where n is the number of nodes in the tree, as we visit each node once.
• 🧺 Space complexity: O(h) where h is the height of the tree, due to the recursion stack.