Solution For Binary Tree Maximum Path Sum

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

Step by Step Implementation For Binary Tree Maximum Path Sum

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxValue;
    
    public int maxPathSum(TreeNode root) {
        maxValue = Integer.MIN_VALUE;
        maxPathDown(root);
        return maxValue;
    }
    
    private int maxPathDown(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, maxPathDown(node.left));
        int right = Math.max(0, maxPathDown(node.right));
        maxValue = Math.max(maxValue, left + right + node.val);
        return Math.max(left, right) + node.val;
    }
}

# 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 1:

# Input: [1,2,3]

#        1
#       / \
#      2   3

# Output: 6
# Example 2:

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

#    -10
#    / \
#   9  20
#     /  \
#    15   7

# Output: 42

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
 
 // recursive function that calculates the maximum path sum 
 // including the node passed in as a parameter
var maxPathSumHelper = function(node) {
    // if the node is null, then there is no path
    if (!node) {
        return 0;
    }
    
    // get the maximum path sum from the left and right subtrees
    let leftSum = maxPathSumHelper(node.left);
    let rightSum = maxPathSumHelper(node.right);
    
    // the maximum path sum that includes the current node is the 
    // maximum of the following three sums:
    // 1. the path sum from the left subtree + the current node
    // 2. the path sum from the right subtree + the current node
    // 3. the path sum from the left subtree + the current node + the path sum from the right subtree
    let maxSum = Math.max(leftSum + node.val, rightSum + node.val, leftSum + rightSum + node.val);
    
    // return the maximum sum
    return maxSum;
};
 
var maxPathSum = function(root) {
    // call the helper function to get the maximum path sum
    return maxPathSumHelper(root);
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int maxSum = INT_MIN; 
        calculateSum(root, maxSum); 
        return maxSum; 
    }
private: 
    int calculateSum(TreeNode* root, int& maxSum) {
        if (!root) return 0; 
        
        int leftSum = calculateSum(root->left, maxSum); 
        int rightSum = calculateSum(root->right, maxSum); 
        
        int currSum = root->val; 
        if (leftSum > 0) currSum += leftSum; 
        if (rightSum > 0) currSum += rightSum; 
        
        maxSum = max(currSum, maxSum); 
        
        return max(root->val, max(root->val + leftSum, root->val + rightSum)); 
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    int maxSum = int.MinValue;
    
    public int MaxPathSum(TreeNode root) {
        FindMaxSum(root);
        return maxSum;
    }
    
    private int FindMaxSum(TreeNode node){
        if(node == null) return 0;
        
        //find the max sum from the left and right sub trees
        int leftMaxSum = FindMaxSum(node.left);
        int rightMaxSum = FindMaxSum(node.right);
        
        //find the max sum that includes the current node
        int maxSumWithNode = node.val + Math.Max(0, leftMaxSum) + Math.Max(0, rightMaxSum);
        
        //update the global max sum
        maxSum = Math.Max(maxSum, maxSumWithNode);
        
        //return the max sum that can be obtained by going through the current node
        return node.val + Math.Max(0, Math.Max(leftMaxSum, rightMaxSum));
    }
}