Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree.

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.

Function Signature:

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(root: TreeNode) -> int:
	    """
	    Find the maximum path sum in the binary tree.

	    Parameters:
	    - root: The root of the binary tree.

	    Returns:
	    - int: The maximum path sum.
	    """
	    # Your code here

Example:

# Example Binary Tree:
#       10
#      / \
#     2   10
#    / \     \
#   20  1    -25
#            / \
#           3   4
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
# Explanation: The maximum path sum is 42 (20 -> 2 -> 10 -> 10)

#      -10
#      / \
#     2   10
#    / \     \
#   20  1    -25
#            / \
#           3   4
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
# Explanation: The maximum path sum is 23 (20 -> 2 -> 1)

#      -10
#      / \
#     2   10
#    / \    \
#   20  1    25
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
# Explanation: The maximum path sum is 47 (20 -> 2 -> -10 -> 10 -> 25)

#      -10
#      / \
#     2   -10
#    / \    \
#  -20  1    25
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 maximum path sum is through one node, 25, only

Note:

  • The given binary tree is not necessarily a binary search tree.
  • All node values are integers.

Instructions:

  • Write the max_path_sum function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊