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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Tree Maximum Path Sum

Difficulty: Hard

Problem Description

Given the root of a binary tree, return the maximum path sum of any non-empty path. A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. The path does not need to pass through the root.

Key Insights

  • A path can start and end at any node in the binary tree, not just the root.
  • The maximum path sum can be calculated using a Depth-First Search (DFS) approach, where we compute the maximum sum for each subtree.
  • At each node, we can choose to either include its left or right subtree in the path or start a new path from that node.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the binary tree, as we visit each node once. Space Complexity: O(H), where H is the height of the tree, due to the recursive call stack.

Solution

To solve this problem, we will use a Depth-First Search (DFS) algorithm. The key idea is to traverse the tree and calculate the maximum path sum at each node. We maintain a global variable to keep track of the maximum path sum found so far.

  1. For each node, compute the maximum path sum that can be obtained from its left and right subtrees.
  2. Calculate the maximum path sum at the current node, which includes the node itself, the left child, and the right child.
  3. Update the global maximum path sum if the current node's maximum path sum is greater.
  4. Return the maximum path sum that can be obtained from the current node to allow its parent to consider it in its path sum.

Code Solutions

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:
        self.max_sum = float('-inf')  # Initialize maximum path sum

        def dfs(node):
            if not node:
                return 0  # Base case: if the node is null, return 0

            # Recursively calculate the maximum path sum for the left and right subtrees
            left_max = max(dfs(node.left), 0)  # Ignore negative sums
            right_max = max(dfs(node.right), 0)

            # Calculate the maximum path sum through the current node
            current_max = node.val + left_max + right_max

            # Update the global maximum path sum
            self.max_sum = max(self.max_sum, current_max)

            # Return the maximum path sum that can be extended to the parent
            return node.val + max(left_max, right_max)

        dfs(root)  # Start DFS from the root
        return self.max_sum  # Return the maximum path sum found
← Back to All Questions