Problem

Given a binary tree, find a maximum path sum from root to a leaf.

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
  
1
2
3

Input: [10, 8, 2, 3, 5, 2, 1]
Output: [10, 8, 5]
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
    C:::maxPath
    G:::maxPath
  
1
2
3

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

Solution

Method 1 - DFS

To find the maximum sum root-to-leaf 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.

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

 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
34

class Solution {
    public List<Integer> maxSumRootToLeaf(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);
        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);
    }
}
 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 maxSumRootToLeaf(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

    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.