Problem

Find the maximum sum leaf to root path in a Binary Tree. Means in all the paths from root to leaves, 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
    C:::maxPath
    G:::maxPath
  
1
2
3

Input: [10, 8, 2, 3, 5, 2, 1]
Output: [10, 2, 1]
Explanation: The maximum sum path from root to leaf is 10 -> 8 -> 5 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
    B:::maxPath
    D:::maxPath
  
1
2
3

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

Solution

Method 1 - DFS

To find the minimum path sum from the root to a leaf in a binary tree, a Depth-First Search (DFS) traversal can be used to explore all paths from the root to each leaf node. By keeping track of the current sum and updating it if a leaf node is reached with a new minimum sum, we can determine the desired path.

Here is the approach:

  1. Tree Traversal: Use DFS to traverse the tree from the root to each leaf node.
  2. Track Minimum Sum: At each node, add its value to the current sum. When a leaf node is reached, update the minimum sum if the current path sum is less than the known minimum 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 smaller.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    public List<Integer> minSumRootToLeaf(TreeNode root) {
        if (root == null) return new ArrayList<>();
        
        List<Integer> minPath = new ArrayList<>();
        List<Integer> currentPath = new ArrayList<>();
        int[] minSum = {Integer.MAX_VALUE};
        
        dfs(root, 0, minSum, minPath, currentPath);
        return minPath;
    }
    
    private void dfs(TreeNode node, int currentSum, int[] minSum, List<Integer> minPath, 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 < minSum[0]) {
                minSum[0] = currentSum;
                minPath.clear();
                minPath.addAll(currentPath);
            }
        } else {
            dfs(node.left, currentSum, minSum, minPath, currentPath);
            dfs(node.right, currentSum, minSum, minPath, currentPath);
        }
        
        currentPath.remove(currentPath.size() - 1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def minSumRootToLeaf(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        self.min_sum = float('inf')
        self.min_path = []
        
        current_path = []
        self.dfs(root, 0, current_path)
        return self.min_path

    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.min_sum:
                self.min_sum = current_sum
                self.min_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.