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 Depth-First Search (DFS) approach to traverse the tree.
2. maxPathSumHelper Function: This recursive function will explore the tree and calculate the maximum path sum starting from a given node. It returns the maximum sum including the current node, either going towards its left or right subtree. It does not necessarily include the parent.
3. maxPathSum Function: This function initializes maxSum to negative infinity. It then calls the recursive helper function and updates maxSum based on the returned values and other potential paths.
4. Base Case: If the current node is null, we return 0 (no contribution to the path sum).
5. Recursive Step:
   • Recursively calculate the maximum path sum from the left and right subtrees using maxPathSumHelper.
   • Update maxSum with the maximum of the following:
     • The current node's value.
     • The current node's value plus the maximum path sum from the left subtree.
     • The current node's value plus the maximum path sum from the right subtree.
     • The current node's value plus the maximum path sums from both left and right subtrees.
   • Return the maximum path sum including the current node (either including the left or right subtree, or just the node itself). This ensures we correctly build paths from leaves upwards.

Explanation

The key idea is that the maximum path sum might not necessarily pass through the root. Therefore, we need to explore all possible paths. The recursive helper function efficiently explores these paths, and the main function ensures the global maximum is tracked. The crucial aspect is handling the case where a path might use both the left and right subtrees of a node.

Code

using System;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    private int maxSum = int.MinValue;

    public int MaxPathSum(TreeNode root) {
        MaxPathSumHelper(root);
        return maxSum;
    }

    private int MaxPathSumHelper(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftMax = Math.Max(0, MaxPathSumHelper(node.left)); // ensures we don't consider negative paths
        int rightMax = Math.Max(0, MaxPathSumHelper(node.right));

        maxSum = Math.Max(maxSum, node.val + leftMax + rightMax); //check for path through node

        return node.val + Math.Max(leftMax, rightMax); //Return the max path including this node, but not necessarily both children
    }
}

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 can be equal to N. In a balanced tree, H is log(N).