Binary tree maximum path sum

We will calculate the sum of left subtree and right subtree and return the value of maximum of them added with the current node value from our recursive DFS method. In the process we will keep track of the maximum sum of both subtree added with the current node value. Once the DFS traversal is done, we will return the maximum sum.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.maxSum = -math.inf

        def dfs(node):
            if not node:
                return 0
            leftSum = max(0, dfs(node.left))
            rightSum = max(0, dfs(node.right))

            self.maxSum = max(self.maxSum, node.val+leftSum+rightSum)

            return max(leftSum, rightSum) + node.val

        dfs(root)
        return self.maxSum

Time Complexity: O(n)
Space Complexity: O(n)