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 to traverse the tree.
2. Base Case: If the current node is null, return 0.
3. Recursive Calls: Recursively call the function on the left and right children.
4. Max Single Path: Calculate the maximum path sum starting from the current node, considering either the left subtree, right subtree, or neither (just the node's value itself). This is crucial: we're looking for the maximum path that includes the current node at its apex, going down only one of its branches.
5. Max Path Sum: Update the global maxPathSum variable with the maximum of the current maxPathSum and the sum of values from the left subtree, right subtree, and the current node's value, if this produces a larger sum. This handles the scenario where the maximum path doesn't include the current node (which may include any subtree, not only left or right).
6. Return Value: Return the maximum single path sum (from step 4) from the current node, to be used for calculations higher up the tree.

Explanation

The key idea is to distinguish between:

• Max Single Path from a Node: The maximum path sum starting from a particular node and going down only one of its branches. This value is needed to update sums for parent nodes.
• Global Max Path Sum: The overall maximum path sum found so far, which considers paths that might start and end at different nodes (not necessarily including the root).

The recursion ensures we explore all possible paths. The maxSinglePath variable during recursion focuses on paths from the current node downwards. The maxPathSum variable keeps track of the overall maximum path found so far across all nodes.

Code

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}

function maxPathSum(root: TreeNode | null): number {
    let maxPathSum = -Infinity;

    function maxGain(node: TreeNode | null): number {
        if (node === null) {
            return 0;
        }

        let leftGain = Math.max(0, maxGain(node.left)); //Avoid negative contributions
        let rightGain = Math.max(0, maxGain(node.right));

        let maxSinglePath = node.val + leftGain + rightGain; //Max path starting from this node

        maxPathSum = Math.max(maxPathSum, maxSinglePath); //Global max

        return Math.max(leftGain, rightGain) + node.val; // Return Max single path from THIS node
    }

    maxGain(root);
    return maxPathSum;
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly 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 could be equal to N. In the best case (a balanced tree), H is log(N).