Binary Tree Maximum Path Sum

98.Binary Tree Maximum Path Sum

Tree

Dynamic Programming

Divide and Conquer

Problem Statement:

Given the root of a binary tree, return the maximum path sum. A path in a binary tree is any sequence of nodes starting from some node and ending at any node (including the starting node and the ending node). The path must contain at least one node and does not need to go through the root.

Algorithm:

1. Use a helper function to calculate the maximum path sum for each subtree.
2. For each node, calculate:
   • The maximum path sum using the left subtree.
   • The maximum path sum using the right subtree.
   • The maximum sum including the current node as the root of the path.
3. Update the global maximum path sum at each step.
4. Return the maximum path sum that can be used by the parent node (either through the left or the right subtree).

Complexity:

Time: O(n), where n is the number of nodes in the tree | Space: O(h), where h is the height of the tree.

Java Implementation:

class Solution {
    public int maxPathSum(TreeNode root) {
        int[] max = new int[1]; // To store the global maximum path sum
        max[0] = Integer.MIN_VALUE; // Initialize with the smallest possible value
        recurse(root, max);
        return max[0];
    }

    private int recurse(TreeNode node, int[] max) {
        if (node == null) return 0; // Base case: null nodes contribute 0 to the sum

        // Recursive postorder traversal
        int left = recurse(node.left, max);
        int right = recurse(node.right, max);

        // Ignore negative sums (similar to Kadane's algorithm)
        left = Math.max(0, left);
        right = Math.max(0, right);

        // Update the global maximum path sum with the sum through this node
        max[0] = Math.max(max[0], left + right + node.val);

        // Return the maximum path sum including this node for its parent
        return Math.max(left, right) + node.val;
    }
}
                

Python Implementation:

class Solution:
    def maxPathSum(self, root):
        self.max_sum = float('-inf')  # Initialize global max path sum
        
        def dfs(node):
            if not node:
                return 0
            
            # Postorder traversal
            left = max(dfs(node.left), 0)  # Ignore negative sums
            right = max(dfs(node.right), 0)  # Ignore negative sums
            
            # Update the global maximum path sum
            self.max_sum = max(self.max_sum, left + right + node.val)
            
            # Return max path sum including the current node for the parent
            return max(left, right) + node.val
        
        dfs(root)
        return self.max_sum
                

C++ Implementation:

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int max_sum = INT_MIN;  // Initialize global max path sum
        dfs(root, max_sum);
        return max_sum;
    }

private:
    int dfs(TreeNode* node, int& max_sum) {
        if (!node) return 0;

        // Postorder traversal
        int left = max(dfs(node->left, max_sum), 0);  // Ignore negative sums
        int right = max(dfs(node->right, max_sum), 0);  // Ignore negative sums

        // Update the global maximum path sum
        max_sum = max(max_sum, left + right + node->val);

        // Return max path sum including the current node for the parent
        return max(left, right) + node->val;
    }
};