Problem Statement

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Additional information

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

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.

Recursive Depth-First Search (Postorder) - Optimal

Intuition

A path can start and end anywhere in the tree. However, every valid path has a "highest" node (the node closest to the root). If we consider any node as this "highest" point of a path, the maximum path sum passing through it would be its own value plus the maximum path sum coming from its left subtree, plus the maximum path sum coming from its right subtree.

Since negative values can decrease the sum, if a subtree's maximum contribution is negative, we should just ignore it (treat it as 0).

There is a catch: when a node returns its maximum contribution to its parent, the path can only go down one branch (either left or right). A path cannot split in two directions. So, the value returned to the parent must be node.val + max(left_contribution, right_contribution).

Algorithm

1. Initialize a global or nonlocal variable res to negative infinity to keep track of the absolute maximum path sum found so far.
2. Create a recursive helper function get_max_gain(node):

• Base Case: If node is None, its contribution is 0.
• Recurse Left: Call get_max_gain(node.left). If the result is negative, we don't want to include it, so take max(result, 0).
• Recurse Right: Call get_max_gain(node.right). Take max(result, 0).
• Update Global Max: The maximum path sum with the current node as the highest point is node.val + left_gain + right_gain. Update res = max(res, current_max_path).
• Return Contribution: To continue the path upwards to the parent, we can only choose one branch. Return node.val + max(left_gain, right_gain).

3. Call get_max_gain(root).
4. Return res.

def max_path_sum(root: Optional[TreeNode]) -> int:
    res = -float('inf')
    
    def get_max_gain(node):
        nonlocal res
        if not node:
            return 0
            
        # Max sum on the left and right sub-trees of node
        # Ignore paths with negative sums, since we need to find the max sum
        left_gain = max(get_max_gain(node.left), 0)
        right_gain = max(get_max_gain(node.right), 0)
        
        # Price to start a new path where `node` is a highest node
        current_max_path = node.val + left_gain + right_gain
        
        # Update the global max
        res = max(res, current_max_path)
        
        # For return, we can only choose one branch
        return node.val + max(left_gain, right_gain)
        
    get_max_gain(root)
    return res

Time & Space Complexity

• Time complexity: O(n)

• Reason: We visit every node in the binary tree exactly once.

• Space complexity: O(h)

• Reason: The space complexity is determined by the height h of the tree due to the recursion stack. In the worst case (a perfectly skewed tree), this is O(n). In a balanced tree, it is O(log n).