Ever wondered how to find the path with the maximum sum in a binary tree? This problem is a favorite among interviewers and a great way to test your understanding of tree traversal and recursive thinking. Let's break it down and solve it step by step!

The Problem Statement

Given a binary tree, we need to find the path that yields the maximum sum. The path can start and end at any node, and it doesn't necessarily need to pass through the root.

For example, consider this binary tree:

       1
      / \
     2   3
    / \
   4   5

The path with the maximum sum is 4 -> 2 -> 5, which adds up to 11.

The Approach

The key to solving this problem lies in using a recursive, bottom-up approach. We'll traverse the tree using depth-first search (DFS) and compute two values for each node:

1. The maximum path sum that includes the node and one of its subtrees (used for the parent's calculation)
2. The maximum path sum in the entire subtree rooted at the node (used to update the overall maximum)

The Algorithm

Here's how we'll tackle this problem:

1. Create a recursive function that takes a node as input.
2. If the node is null, return 0.
3. Recursively calculate the maximum path sum for the left and right subtrees.
4. Calculate the maximum path sum including the current node:
   • For the parent's calculation: max(node.val, node.val + max(leftSum, rightSum))
   • For the overall maximum: max(node.val, node.val + leftSum, node.val + rightSum, node.val + leftSum + rightSum)
5. Update the global maximum if necessary.
6. Return the maximum path sum for the parent's calculation.

Java Implementation

Let's implement this algorithm in Java:

class Solution {
    int maxSum = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        maxPathSumHelper(root);
        return maxSum;
    }
    
    private int maxPathSumHelper(TreeNode node) {
        if (node == null) return 0;
        
        int leftSum = Math.max(maxPathSumHelper(node.left), 0);
        int rightSum = Math.max(maxPathSumHelper(node.right), 0);
        
        int pathSum = node.val + leftSum + rightSum;
        maxSum = Math.max(maxSum, pathSum);
        
        return node.val + Math.max(leftSum, rightSum);
    }
}

Let's break down this implementation:

• We use a class variable maxSum to keep track of the overall maximum path sum.
• The maxPathSum method is our entry point, which calls the helper method and returns the final result.
• In maxPathSumHelper, we first handle the base case of a null node.
• We recursively calculate the maximum sum for left and right subtrees, using Math.max(sum, 0) to avoid negative sums.
• We calculate the path sum through the current node and update maxSum if necessary.
• Finally, we return the maximum sum that includes the current node and one of its subtrees.

Time and Space Complexity

• Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node once.
• Space Complexity: O(h), where h is the height of the tree. This space is used by the recursion stack.

Common Pitfalls

When solving this problem, watch out for these common mistakes:

1. Forgetting to handle negative values: Sometimes, it's better not to include a subtree if its sum is negative.
2. Not updating the global maximum at each node: The maximum path might not include the root.
3. Returning the wrong value from the recursive function: Remember, we return the max sum including the current node and at most one child, not the overall maximum path sum.

Conclusion

The Maximum Path Sum problem is a great example of how recursive thinking can solve complex tree problems. By breaking down the problem into subproblems and combining their solutions, we can efficiently find the answer.