Binary Tree Maximum Path Sum [Solution]

To solve the “Binary Tree Maximum Path Sum” problem, we can use a recursive approach to find the maximum path sum at each node and update the global maximum as we traverse the tree.

Here’s the implementation:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def max_path_sum(self, root: TreeNode) -> int:
        # Initialize a variable to store the maximum path sum
        self.max_sum = float('-inf')

        def max_gain(node: TreeNode) -> int:
            if not node:
                return 0

            # Recursively calculate the maximum gain from the left and right subtrees
            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)

            # Update the maximum path sum considering the current node
            current_sum = node.val + left_gain + right_gain
            self.max_sum = max(self.max_sum, current_sum)

            # Return the maximum gain for the current node's parent
            return node.val + max(left_gain, right_gain)

        # Start the recursive traversal from the root
        max_gain(root)
        return self.max_sum

# Example usage:
solution = Solution()
tree = TreeNode(10,
                TreeNode(2, 
                	     TreeNode(20), 
                	     TreeNode(1)),
                TreeNode(10, 
                	     None, 
                	     TreeNode(-25, 
                	     	      TreeNode(3), 
                	     	      TreeNode(4))))
result = solution.max_path_sum(tree)  
print(result)
assert result == 42

tree = TreeNode(-10,
                TreeNode(2, 
                	     TreeNode(20), 
                	     TreeNode(1)),
                TreeNode(10, 
                	     None, 
                	     TreeNode(-25, 
                	     	      TreeNode(3), 
                	     	      TreeNode(4))))
result = solution.max_path_sum(tree)  
print(result)
assert result == 23

tree = TreeNode(-10,
                TreeNode(2, 
                	     TreeNode(20), 
                	     TreeNode(1)
                	     ),
                TreeNode(10, 
                	     None, 
                	     TreeNode(25)
                	     )
                )
result = solution.max_path_sum(tree)  
print(result)
assert result == 47

tree = TreeNode(-10,
                TreeNode(2, 
                	     TreeNode(-20), 
                	     TreeNode(1)
                	     ),
                TreeNode(-10, 
                	     None, 
                	     TreeNode(25)))
result = solution.max_path_sum(tree)  
print(result)
assert result == 25

Explanation:

• The max_path_sum function is a method of the Solution class. It initializes a variable max_sum to store the maximum path sum encountered during the traversal.
• The max_gain function calculates the maximum gain (maximum sum) achievable from a node considering its left and right subtrees. It returns the maximum gain for the current node’s parent.
• During the traversal, the current sum including the current node is calculated (node.val + left_gain + right_gain). If this sum is greater than the current max_sum, it is updated.
• The final result is the maximum path sum found during the traversal.

Time Complexity:

The time complexity is O(N), where N is the number of nodes in the binary tree. We visit each node once during the traversal.

Space Complexity:

The space complexity is O(H), where H is the height of the binary tree. This is the maximum depth of the recursive call stack. In the worst case, the depth of the recursion is equal to the height of the tree.