Problem Explanation

The problem is asking us to find the maximum path sum in a non-empty binary tree. A path is defined as a sequence of nodes from one starting node to another node in the tree following the parent-child connections. The path must contain at least one node and does not need to go through the root.

To understand the problem clearly, let's look at an example:

Example 1:

Input: [1,2,3]

1
2
3       1
4      / \
5     2   3

Here, the maximum path sum will be 6 (i.e., 1+2+3).

Solution Approach

The solution uses a depth-first search (DFS) approach, where for each node, we compute the maximum path sum that includes the node and its one subtree (either left or right). We keep on updating the maximum path sum seen so far. At each node, we return the maximum path sum from that node, including one of its subtrees, to its parent.

ASCII illustration for DFS in the example tree above would be like:

1
2
3  1
4 / \
5v   v
62   3

Starting from the node 1, DFS first visits the left child 2, then returns to 1, and then visit the right child 3.

Let's step through the example 1 with the solution approach:

Step 1: Start with the root node, which is 1. Compute the maximum path sum that can be obtained by:

• just the root node value,
• root node value plus the maximum path sum from its left child,
• root node value plus the maximum path sum from its right child

In this case, the value is 1 + max(0,2) + max(0,3) = 6. We update the maximum path sum as 6.

The function then returns the maximum path sum starting from that node including one of its subtrees, which is 1+max(0,3)=4.

Solution in different languages

Here is the solution in different programming languages.

Python

1
2python
3class Solution:
4    def maxPathSum(self, root):
5        self.maximum = float('-inf')
6        self.maxPathSumFrom(root)
7        return self.maximum
8    
9    def maxPathSumFrom(self, node):
10        if not node:
11            return 0
12        leftSum = max(0, self.maxPathSumFrom(node.left))
13        rightSum = max(0, self.maxPathSumFrom(node.right))
14        self.maximum = max(self.maximum, leftSum + rightSum + node.val)
15        return max(leftSum, rightSum) + node.val

Java

1
2java
3class Solution {
4    int maxSum = Integer.MIN_VALUE;
5
6    public int maxPathSum(TreeNode root) {
7        maxPathSumFrom(root);
8        return maxSum;
9    }
10
11    private int maxPathSumFrom(TreeNode root) {
12        if (root == null) return 0;
13        int leftSum = Math.max(0, maxPathSumFrom(root.left));
14        int rightSum = Math.max(0, maxPathSumFrom(root.right));
15        maxSum = Math.max(maxSum, leftSum + rightSum + root.val);
16        return Math.max(leftSum, rightSum) + root.val;
17    }
18}

JavaScript

1
2javascript
3var maxPathSum = function(root) {
4    let maxSum = Number.MIN_SAFE_INTEGER;
5    function maxPathSumFrom(node) {
6        if (node == null) return 0;
7        let leftSum = Math.max(0, maxPathSumFrom(node.left));
8        let rightSum = Math.max(0, maxPathSumFrom(node.right));
9        maxSum = Math.max(maxSum, leftSum + rightSum + node.val);
10        return  Math.max(leftSum, rightSum) + node.val;
11    }
12    maxPathSumFrom(root);
13    return maxSum;
14};

C++

1
2cpp
3class Solution {
4public:
5    int maxPathSum(TreeNode* root) {
6        int maxSum = INT_MIN;
7        maxPathSumFrom(root, maxSum);
8        return maxSum;
9    }
10    
11private:
12    int maxPathSumFrom(TreeNode* root, int& maxSum) {
13        if(root == NULL) return 0;
14        int leftSum = max(0, maxPathSumFrom(root->left, maxSum));
15        int rightSum = max(0, maxPathSumFrom(root->right, maxSum));
16        maxSum = max(maxSum, leftSum + rightSum + root->val);
17        return max(leftSum, rightSum) + root->val;
18    }
19};

C#

1
2csharp
3public class Solution {
4    private int maxSum;
5    public int MaxPathSum(TreeNode root) {
6        maxSum = int.MinValue;
7        MaxPathSumFrom(root);
8        return maxSum;
9    }
10    
11    private int MaxPathSumFrom(TreeNode root) {
12        if (root == null) return 0;
13        int leftSum = Math.Max(0, MaxPathSumFrom(root.left));
14        int rightSum = Math.Max(0, MaxPathSumFrom(root.right));
15        maxSum = Math.Max(maxSum, leftSum + rightSum + root.val);
16        return Math.Max(leftSum, rightSum) + root.val;
17    }
18}

All solutions follow a similar pattern. We initialize a class variable maxSum to very small value. Then, call a recursive function maxPathSumFrom(root), where for each node, we calculate the maximum path sum that includes that node and update the maxSum. We ultimately return maxSum which gives us the maximum path sum in the binary tree.## Conclusion

The maximum path sum problem in a binary tree is a classic tree processing problem that requires understanding the properties of binary trees and how to traverse them. The depth-first search (DFS) approach is extremely useful in this, and similar, problems.

As seen in the example solution above, we have solved this problem in Python, Java, JavaScript, C++, and C#. Each solution follows the same basic strategy of maintaining a running maximum sum and recursively processing each node's subtrees.

The most important aspect of this solution is correctly defining the base case (an empty node should return 0), identifying the maximum path sum that includes each node (the node value, plus the maximum possible sum from either of its subtrees), and then determining the new maximum sum so far.

In all languages, the time complexity of this solution is O(n), where n is the number of nodes in the tree. This is because each node in the tree is processed exactly once. Thus, this solution is very efficient and can handle large inputs.

Also, this problem helps to understand how to approach tree-based problems and how to effectively traverse and process tree nodes.

In conclusion, the maximum path sum problem in a binary tree is not only an important problem for understanding tree processing, but it also serves as a conceptual foundation for many other tree-based problems in computer science and programming interviews. The logic learned here can be expanded and adapted to solve many such related problems.