Binary Tree Maximum Path Sum - Leetcode Solution

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:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

Solution:

This problem can be solved using recursion. The idea is to compute the maximum sum path going through each node and return the maximum of those values.

For each node in the tree, we keep track of four values:

1. val: The value of the node itself.
2. left: The maximum sum path that starts from the left child of this node.
3. right: The maximum sum path that starts from the right child of this node.
4. maxSum: The maximum sum path that starts from this node and goes down to some leaf node.

The base case for recursion is when the root is null, in which case we return 0 for all the four values.

Now let's look at the recursion case. We first recursively compute the left and right values for the current node using the same approach. If either of the left or right values is negative, we set that value to 0, since we don't want to add negative numbers to the sum. We then compute the maxSum for the current node as the sum of the value of the node, left, and right.

However, we cannot just return the maxSum for the current node as the answer, because the path may not go through the current node. It could go through the parent of the current node. Therefore, we compute the sumPath for the current node as the maximum of the value of the current node, or the value of the current node plus the maximum of left and right.

We then update the overall maximum sum if the maxSum for this node is greater than the current maximum sum.

Finally, we return the sumPath for the current node.

Here is the Python code for the same:

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        def helper(node):
            # Base case: If the node is null, return 0 for all values.
            if not node:
                return 0, 0, 0, float('-inf')
            
            # Recursively compute left and right values
            left_val, left_sum_path, left_max_path, _ = helper(node.left)
            right_val, right_sum_path, right_max_path, _ = helper(node.right)
            
            # Set negative values to 0
            left_max_path = max(left_max_path, 0)
            right_max_path = max(right_max_path, 0)
            
            # Compute maxSum and update global maximum if necessary
            maxSum = node.val + left_max_path + right_max_path
            self.max_sum = max(self.max_sum, maxSum)
            
            # Compute sumPath for current node
            sumPath = max(node.val, node.val + max(left_max_path, right_max_path))
            
            # Compute overall maximum path sum for this node
            max_path = max(left_max_path, right_max_path) + node.val
            
            return node.val, sumPath, max(max_path, 0), maxSum
        
        # Initialize maximum sum to minimum integer value
        self.max_sum = float('-inf')
        
        # Call helper function on root and return the maximum sum
        _, _, _, res = helper(root)
        return res if self.max_sum == float('-inf') else self.max_sum

Time Complexity: O(n)

Space Complexity: O(h), where h is the height of the tree

1