Binary Tree Maximum Path Sum hard

Problem Statement

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1

Input: root = [1,2,3] Output: 6 Explanation: The maximum path sum is 1 + 2 + 3 = 6.

Example 2

Input: root = [-10,9,20,null,null,15,7] Output: 42 Explanation: The maximum path sum is 15 + 20 + 7 = 42.

Steps

1. Recursive Approach: We'll use a recursive function maxPathDown that calculates the maximum path sum starting from a given node and going downwards. This path must end at the node itself.

2. Base Case: If the node is null, return 0.

3. Recursive Calls: Recursively calculate the maximum path sum from the left and right children (maxPathDown(root.left) and maxPathDown(root.right)).

4. Max Path Down: The maximum path sum starting from the current node and going downwards is the current node's value plus the maximum of the left and right path sums (we only consider downwards paths, not paths going up). We need to consider the case that the maximum path sum from the left or right might be negative. We only include these paths if they contribute positively to the total. We make sure we do not add anything to the maximum path if the path from a subtree is negative.

5. Global Maximum: Maintain a global variable maxSum to store the maximum path sum found so far. Update maxSum if the current path sum (including paths potentially going up to parents) is greater. This is the key step that captures paths that aren't necessarily downwards only. It sums the max paths from left and right along with the current node value.

6. Return Value: The function maxPathDown returns the maximum path sum starting from the current node and going downwards, which is used by the parent's call to recursively calculate the overall max path.

Explanation

The algorithm cleverly uses recursion to explore all possible paths. maxPathDown finds the maximum path ending at a given node. The global maxSum variable keeps track of the overall maximum path sum found during the entire traversal. The key insight is that the maximum path might not necessarily pass through the root. It could be a path within a subtree. The algorithm efficiently handles negative node values as well.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxPathDown(root);
        return maxSum;
    }

    private int maxPathDown(TreeNode root) {
        if (root == null) return 0;

        int left = Math.max(0, maxPathDown(root.left));  //Consider only positive contributions
        int right = Math.max(0, maxPathDown(root.right)); //Consider only positive contributions

        maxSum = Math.max(maxSum, left + right + root.val); //Update global max including paths going up

        return Math.max(left, right) + root.val; //Return max path from current node going down
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N. In the best case (a balanced tree), H is log(N).