Binary Tree Maximum Path Sum

Problem Statement

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. (link)

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

• The number of nodes in the tree is in the range [1, 3 * 10<sup>4</sup>].

• -1000 <= Node.val <= 1000

Solution

To understand the logic, assume that there are 3 nodes in the tree: one parent, one right child, and one left child. The maximum path that can be obtained from the root will be root + left child + right child, provided both the left child and right child are positive. We don't add to the max path if any child is negative.

Similarly, we calculate the maximum path for all the nodes and store the global maximum in a variable.

Note: When returning the path sum from a particular node, we cannot add both the left path sum and the right path sum. We can only add either the left or the right because this path will be part of the parent path, making it impossible to include both.

Code

class Solution {
    private int maxSum;

    private int calculatePathSum(TreeNode root) {
        if(root == null) return 0;


        int leftSum = Math.max(0,calculatePathSum(root.left));
        int rightSum = Math.max(0,calculatePathSum(root.right));

        maxSum = Math.max(maxSum, root.val+leftSum+rightSum);
        return root.val + Math.max(leftSum, rightSum);
    }

    public int maxPathSum(TreeNode root) {
        maxSum = root.val;
        calculatePathSum(root);
        return maxSum;
    }
}

Complexity

Time - O(n)

Space - O(n)