We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Binary Tree Maximum Path Sum

Number: 124

Difficulty: Hard

Paid? No

Companies: DoorDash, Amazon, Meta, Google, Oracle, Yandex, Salesforce, Microsoft, TikTok, Nutanix, Flipkart, Arista Networks, tcs, Datadog, Nvidia, Citadel, Apple, Adobe, Uber, Snap, Booking.com, Intuit, Walmart Labs, Arcesium, Patreon, Baidu, Wix

Problem Description

Given a binary tree where each node contains an integer value, the goal is to determine the path that produces the maximum sum. A path is defined as any sequence of nodes connected by edges, where each node appears at most once, and the path does not necessarily pass through the root. The path sum is the total of all the node values on that path.

Key Insights

  • Use Depth-First Search (DFS) to explore the tree in a post-order fashion.
  • For each node, calculate the maximum gain including that node and optionally one of its subtrees.
  • A node’s best contribution to its parent can be either just its own value or its value plus the maximum gain from either the left or right child.
  • Update a global maximum path sum that considers the possibility of combining both left and right gains with the current node.
  • Handle negative values by comparing gains against 0 to avoid decreasing the path sum.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, since each node is visited exactly once.
Space Complexity: O(n) in the worst-case scenario due to the recursion stack (O(H) where H is the height of the tree, which can be O(n) for skewed trees).

Solution

We use a recursive DFS approach (post-order traversal) to compute the maximum gain from each subtree. For every node:

  1. Recursively compute the maximum gain from the left and right child, ensuring that negative gains are treated as 0.
  2. The maximum gain that can be provided to the node’s parent is the node’s value plus the larger gain from its left or right child.
  3. Simultaneously, the potential maximum path sum including the current node as the highest (or root) node is the node’s value plus both left and right gains.
  4. Update a global variable that holds the maximum path sum found so far.
  5. Return the maximum gain (node value plus one best child) to be used by the node’s parent.

This strategy ensures that every possible path sum is considered while avoiding double-counting nodes.

Code Solutions

# 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: TreeNode) -> int:
        # Initialize global maximum path sum with a very small number
        self.global_max = float('-inf')
        
        def dfs(node: TreeNode) -> int:
            if not node:
                return 0
            
            # Recursively calculate max gain from left and right children, discard negative gains
            left_gain = max(dfs(node.left), 0)
            right_gain = max(dfs(node.right), 0)
            
            # Current maximum including both left and right gains
            current_max = node.val + left_gain + right_gain
            
            # Update global maximum path sum if current_sum is higher
            self.global_max = max(self.global_max, current_max)
            
            # Return the node's value plus the max of one child gain (only one side can be chosen for parent path)
            return node.val + max(left_gain, right_gain)
        
        dfs(root)
        return self.global_max
← Back to All Questions