Binary Tree Maximum Path Sum

Let's dive into the problem of finding the maximum path sum in a binary tree. This is a classic tree traversal problem where we need to consider paths that might not necessarily pass through the root.

1. Naive (Brute Force) Solution

The most straightforward approach would be to consider every possible path in the tree, calculate its sum, and then return the maximum sum found. We can recursively explore all subtrees and compute path sums starting from each node.

Algorithm:

For each node, consider it as the potential starting/ending point of a path.
Recursively explore left and right subtrees.
Calculate the path sum from the current node down to all leaf nodes in both subtrees.
Calculate the path sum of paths that include the left subtree, the node itself, and the right subtree.
Keep track of the maximum path sum encountered so far.

Code (Python):

python class TreeNode: def init(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right

def maxPathSum_naive(root): max_sum = float('-inf')

def path_sum_from_node(node):
    nonlocal max_sum
    if not node:
        return 0
    
    # Calculate path sum from the current node going down to the left
    left_sum = path_sum_from_node(node.left) if node.left else 0
    
    # Calculate path sum from the current node going down to the right
    right_sum = path_sum_from_node(node.right) if node.right else 0

    # Path that only includes this node:
    current_sum = node.val
    max_sum = max(max_sum, current_sum)
    
    # Path that includes the left subtree, this node:
    left_path = current_sum + left_sum
    max_sum = max(max_sum, left_path)
    
    # Path that includes the right subtree, this node
    right_path = current_sum + right_sum
    max_sum = max(max_sum, right_path)
    
    # Path that includes the left subtree, this node, the right subtree:
    left_right_path = current_sum + left_sum + right_sum
    max_sum = max(max_sum, left_right_path)

    return max(node.val + max(left_sum, right_sum, 0), node.val)

path_sum_from_node(root)

return max_sum

Example Usage:

root = TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))

print(maxPathSum_naive(root)) # Output: 42

Big(O) Analysis (Naive):

Time Complexity: O(N^2) in the worst case where N is the number of nodes. This is because for each node, we may be traversing its subtrees.
Space Complexity: O(H), where H is the height of the tree, due to the recursive calls. In the worst case (skewed tree), H = N, so O(N).

2. Optimal Solution

A more efficient approach involves a single traversal of the tree. The key idea is to calculate the maximum path sum including the current node and update the global maximum during the traversal.

Algorithm:

Perform a Depth-First Search (DFS) on the tree.
For each node, recursively calculate the maximum path sum in its left and right subtrees.
If the path sum from either subtree is negative, discard it (as it would decrease the overall sum).
The maximum path sum at the current node is the sum of the node's value and the maximum path sums from its left and right subtrees (excluding negative sums).
Update the global maximum path sum if the current path sum is greater.
Return the maximum path sum that can be extended upwards (i.e., the node's value plus the maximum of the left or right subtree sums).

Code (Python):

python class TreeNode: def init(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right

def maxPathSum(root): max_sum = float('-inf')

def max_path_down(node):
    nonlocal max_sum
    if not node:
        return 0

    left_sum = max(max_path_down(node.left), 0)
    right_sum = max(max_path_down(node.right), 0)

    price_newpath = node.val + left_sum + right_sum

    max_sum = max(max_sum, price_newpath)

    return node.val + max(left_sum, right_sum)

max_path_down(root)
return max_sum

Example Usage:

root = TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))

print(maxPathSum(root)) # Output: 42

Big(O) Analysis (Optimal):

Time Complexity: O(N), where N is the number of nodes. We visit each node exactly once.
Space Complexity: O(H), where H is the height of the tree, due to the recursive calls. In the worst case (skewed tree), H = N, so O(N). In the best case (balanced tree) H = log N so O(log N).

3. Edge Cases

Empty Tree: If the tree is empty (root is None), the maximum path sum is 0 or negative infinity depending on the context of the problem (some problems may state that the tree is non-empty).
Single Node Tree: If the tree consists of a single node, the maximum path sum is the value of that node.
All Negative Values: If all nodes have negative values, the maximum path sum would be the largest negative value (i.e., the node with the smallest absolute value).
Paths Not Through Root: The optimal solution correctly handles paths that do not necessarily pass through the root node.

4. Explanation

The optimal solution leverages the concept of dynamic programming by calculating the maximum path sum from each node to its descendants. By keeping track of a global maximum, it ensures that the final result represents the overall maximum path sum in the entire tree. Discarding negative path sums from subtrees optimizes the search for the maximum path, as negative contributions will always decrease the overall sum.