Let’s break down the approach and then provide a Java example.

Principle

1. Define a Path as Root-to-Leaf: A path in this case is defined from the root node down to any leaf node (a node with no children).

2. Calculate Path Sums Recursively: Use a recursive function to traverse each path and accumulate the sum of node values along that path.

3. Track the Maximum Sum: Keep track of the maximum sum encountered so far, updating it if a higher sum is found on a new path.

4. Return the Maximum Sum Path: After completing all root-to-leaf paths, the algorithm should return the highest sum along with the nodes in that path.

Example in Java

Here’s how you could implement it:

import java.util.ArrayList;

import java.util.List;

class TreeNode {

    int val;

    TreeNode left, right;

    TreeNode(int x) { val = x; }

}

public class MaxSumPathBST {

    // Wrapper class to hold the result

    static class Result {

        int maxSum = Integer.MIN_VALUE;

        List<Integer> maxPath = new ArrayList<>();

    }

    public List<Integer> maxSumPath(TreeNode root) {

        Result result = new Result();

        List<Integer> currentPath = new ArrayList<>();

        findMaxSumPath(root, 0, currentPath, result);

        return result.maxPath;

    }

    private void findMaxSumPath(TreeNode node, int currentSum, List<Integer> currentPath, Result result) {

        if (node == null) return;

        // Add the current node to the path and update the sum

        currentPath.add(node.val);

        currentSum += node.val;

        // If it's a leaf node, check if the current sum is the maximum

        if (node.left == null && node.right == null) {

            if (currentSum > result.maxSum) {

                result.maxSum = currentSum;

                result.maxPath = new ArrayList<>(currentPath);

            }

        } else {

            // Recur for left and right subtrees

            findMaxSumPath(node.left, currentSum, currentPath, result);

            findMaxSumPath(node.right, currentSum, currentPath, result);

        }

        // Backtrack: remove the current node from the path

        currentPath.remove(currentPath.size() - 1);

    }

    public static void main(String[] args) {

        // Sample tree:

        //        10

        //       /  \

        //      5    20

        //     / \     \

        //    3   7     30

        TreeNode root = new TreeNode(10);

        root.left = new TreeNode(5);

        root.right = new TreeNode(20);

        root.left.left = new TreeNode(3);

        root.left.right = new TreeNode(7);

        root.right.right = new TreeNode(30);

        MaxSumPathBST bst = new MaxSumPathBST();

        List<Integer> maxSumPath = bst.maxSumPath(root);

        System.out.println("Path with maximum sum: " + maxSumPath);

    }

}

Explanation

1. Result Class: Result is a helper class that keeps track of the maximum sum (maxSum) and the corresponding path (maxPath) throughout the recursion.

2. Recursive Function (findMaxSumPath):

• Accumulate Sum: Each call adds the node’s value to currentSum and includes the node in currentPath.

• Check Leaf Node: When reaching a leaf node, compare the current path sum with the maxSum. If it’s higher, update maxSum and copy the current path to maxPath.

• Backtracking: After the recursion explores both left and right children, the node is removed from currentPath to backtrack, ensuring paths are unique per recursion call.

3. Output:

• The maxSumPath function returns the path (as a list of integers) that corresponds to the maximum sum from root to leaf.

Example Execution

For a BST like this:

        10

       /  \

      5    20

     / \     \

    3   7     30

The path with the maximum sum is 10 -> 20 -> 30, which sums to 60.

Complexity

• Time Complexity: , where  is the number of nodes. This is because each node is visited once.

• Space Complexity: , where  is the height of the tree, due to the recursion stack and path storage.