Maximum Path Sum Binary Tree III

Given a binary tree in which each node contains an integer number. Find the maximum possible subpath sum(both the starting and ending node of the subpath should be on the same path from root to one of the leaf nodes, and the subpath is allowed to contain only one node).

Assumptions

• The root of given binary tree is not null

Examples

-5

/ \

2 11

/ \

6 14

/

-3

The maximum path sum is 11 + 14 = 25

Solution: Recursive bottom up

Base case: root == null; return 0

From Children: get max value path to root

At current level: pick highest value between (root, root + left, root + right). Update global max

To parent: return path picked

public int maxSumPath(Node root, int[] solution){
    if (root == null) return 0;
    
    int left = maxSumPath(root.left, solution);
    int right = maxSumPath(root.right, solution);
    
    int localBestPath = Math.max(root.key, root.key + Math.max(left, right);
    
    solution[0] = Math.max(solution[0], localBestPath);
    
    return localBestPath;
}

TC: O(N)

SC: O(Log(N))