Binary Tree Maximum Path Sum [Hard, PostORder]

124.Binary Tree Maximum Path Sum

Tree

Binary Tree

Depth-First Search

Dynamic Programming

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. Find the path with the maximum sum. The path may start and end at any nodes in the tree.

Example:

Input:

root = [-10,9,20,null,null,15,7]

→

Output:

42

The optimal path is 15 -> 20 -> 7 with sum = 42

Algorithm:

1. Use post-order traversal (left, right, node)
2. At each node, calculate max path through it
3. For parent path, choose max of left or right subtree
4. Use Kadane's concept to ignore negative sums

Complexity:

Time: O(n) | Space: O(h) where h is height of tree

Java Solution:

public int maxPathSum(TreeNode root) {
    int[] max = new int[1];
    max[0] = Integer.MIN_VALUE;
    
    recurse(root, max);
    
    return max[0];
}

private int recurse(TreeNode node, int[] max) {
    // Base case: null node
    if (node == null) return 0;
    
    // Get max path sums from left and right subtrees
    int l = recurse(node.left, max);
    int r = recurse(node.right, max);
    
    // Use 0 instead if path sum is negative (Kadane's)
    l = Math.max(0, l);
    r = Math.max(0, r);
    
    // Update max path sum including current node as turning point
    max[0] = Math.max(max[0], l + r + node.val);
    
    // Return max path sum if this node is part of parent's path
    // Rememeber you can only include left OR right to be used by parent
    // ( So it remains a path)
    return Math.max(l, r) + node.val;
}

Python Solution:

def maxPathSum(self, root: Optional[TreeNode]) -> int:
    max_sum = [float('-inf')]
    
    def recurse(node):
        # Base case: null node
        if not node:
            return 0
            
        # Get max path sums from left and right subtrees
        left = recurse(node.left)
        right = recurse(node.right)
        
        # Use 0 instead if path sum is negative (Kadane's)
        left = max(0, left)
        right = max(0, right)
        
        # Update max path sum including current node as turning point
        max_sum[0] = max(max_sum[0], left + right + node.val)
        
        # Return max path sum if this node is part of parent's path
        return max(left, right) + node.val
        
    recurse(root)
    return max_sum[0]

C++ Solution:

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int maxSum = INT_MIN;
        recurse(root, maxSum);
        return maxSum;
    }
    
private:
    int recurse(TreeNode* node, int& maxSum) {
        // Base case: null node
        if (!node) return 0;
        
        // Get max path sums from left and right subtrees
        int left = recurse(node->left, maxSum);
        int right = recurse(node->right, maxSum);
        
        // Use 0 instead if path sum is negative (Kadane's)
        left = max(0, left);
        right = max(0, right);
        
        // Update max path sum including current node as turning point
        maxSum = max(maxSum, left + right + node->val);
        
        // Return max path sum if this node is part of parent's path
        return max(left, right) + node->val;
    }
};