Binary Tree Maximum Path Sum

Problem Statement

In this problem, you are provided with the root of a binary tree. The task is to determine the maximum sum of values found on any path within this tree. A path is defined here as a sequence of nodes connected directly by edges, and uniquely, any given node can be used at most once in any path. Additionally, the path you consider does not necessarily need to start or end at the root of the tree. You need to calculate the sum of the node values for various possible paths and return the highest sum from among them.

Examples

Example 1

Input:

root = [1,2,3]

Output:

6

Explanation:

The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2

Input:

root = [-10,9,20,null,null,15,7]

Output:

42

Explanation:

The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints

• The number of nodes in the tree is in the range [1, 3 * 104].
• -1000 <= Node.val <= 1000

Approach and Intuition

1. The primary challenge of this problem is to determine the maximum sum path that can start and end at any node, not being restricted to paths crossing the tree's root. Each node offers two main possibilities:

   • It serves as a turning point in the path, implying that the path could span from one of its children, through itself, reaching possibly into the other child.
   • It acts merely as part of a longer path that disregards this node as a junction.

2. Recursion is a natural approach here:

   • At each node, calculate the maximum path sum for paths that pass through but do not necessarily end at that node.
   • This involves considering the node's value itself and the maximum sums of paths extending from either of its children (these paths would naturally extend only downwards).

3. Implementing the recursive function:

   • For each node, determine the maximum contributions from the left and right children separately.
   • Calculate the value for the path passing through the node by taking its value and adding the positive contributions from both sides.
   • Update the global maximum path sum at each step if this new sum is larger.

4. The recursive function will return the maximum sum of paths that can extend from a given node to its parent node. This means, for any node, it returns the maximum of:

   • The node's value alone (considering paths that might just start and end at this node).
   • The node's value plus the maximum extension either left or right, whichever is greater (for paths that extend upward through this node).

5. Use a helper function that recursively carries out these steps, updating a global or externally scoped variable that tracks the maximum found at any node.

By following this recursive approach, you make sure every possible path's sum is calculated without repetitive processing, due to the nature of recursion which inherently covers all nodes and paths. This approach systematically and efficiently find the maximum path sum in the given binary tree.

Solutions

class Solution {
public:
    int findMaxPath(TreeNode* node) {
        highestSum = INT_MIN;
        calculateMaxSubtreeSum(node);
        return highestSum;
    }
    
private:
    int highestSum;
    int calculateMaxSubtreeSum(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }
        int leftMax = max(calculateMaxSubtreeSum(node->left), 0);
        int rightMax = max(calculateMaxSubtreeSum(node->right), 0);
        highestSum = max(highestSum, leftMax + rightMax + node->val);
        return max(leftMax + node->val, rightMax + node->val);
    }
};