Binary Tree Maximum Path Sum hard

Problem Statement

Given a non-empty binary tree, find the maximum path sum.

For this problem, 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.

Example 1

Input: root = [1,2,3] Output: 6 Explanation: The maximum path sum is 1 + 2 + 3 = 6.

Example 2

Input: root = [-10,9,20,null,null,15,7] Output: 42 Explanation: The maximum path sum is 15 + 20 + 7 = 42.

Steps

  1. Recursive Approach: We'll use a recursive function to traverse the tree.
  2. Base Case: If the node is None, return 0.
  3. Recursive Calls: Recursively calculate the maximum path sum from the left and right subtrees.
  4. Max Single Side Path: Calculate the maximum path sum that starts at the current node and goes down only one side (either left or right). This is max(0, left_max + node.val, right_max + node.val). We use max(0, ...) because a negative path sum should be considered as 0 (we don't want to extend a path that decreases the overall sum).
  5. Max Path Through Node: Calculate the maximum path sum that goes through the current node (potentially using both left and right subtrees). This is max_single_side + node.val + max(0, left_max, right_max). We add the max(0, left_max, right_max) to include the maximum contribution from the other side, handling the case where one branch contributes a negative value.
  6. Update Global Maximum: Update the global maximum max_sum if a larger path sum is found.
  7. Return Value: Return the maximum single-side path sum starting at this node. This is crucial for the recursive calls to correctly calculate path sums that may not include the current node as the root of the path.

Explanation

The key idea is to separate the calculation of the maximum path sum through a node from the maximum path sum starting at a node. The function returns the maximum path sum starting at a node, but it keeps track of the global maximum path sum (which might not start at the root). The max_single_side variable is crucial because it helps to propagate information up the tree about the maximum sum achievable starting from a child node, regardless of whether that maximum sum involves further going down the tree from there.

Code

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: TreeNode) -> int:
        max_sum = float('-inf')  # Initialize with negative infinity

        def dfs(node):
            nonlocal max_sum  # Access and modify the global variable
            if not node:
                return 0

            left_max = dfs(node.left)
            right_max = dfs(node.right)

            max_single_side = max(0, left_max + node.val, right_max + node.val)
            max_path_through_node = max_single_side + max(0, left_max, right_max) + node.val

            max_sum = max(max_sum, max_path_through_node)

            return max_single_side

        dfs(root)
        return max_sum

Complexity

  • Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
  • Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N. In a balanced tree, H is logâ‚‚(N).