Binary Tree Maximum Path Sum | Leetcode 124 | Detailed Recursive Solution

You are given the root of a binary tree. Your task is to find the maximum path sum in the tree.

• A path is any sequence of nodes where each pair of adjacent nodes is connected by an edge.
• A path does not need to pass through the root.
• The path must contain at least one node.

The path sum is the sum of the node values along that path.
We want to maximize this path sum.

Here’s the [Problem Link] to begin with.

Examples

Example 1

Input: root = [1,2,3]

        1
       / \
      2   3

Output: 6
Explanation: The path 2 → 1 → 3 has sum 6.

Example 2

Input: root = [-10,9,20,null,null,15,7]

        -10
        /  \
       9    20
           /  \
          15   7

Output: 42
Explanation: The path 15 → 20 → 7 has sum 42.

Intuition and Approach

This problem is trickier than a simple tree sum because a maximum path can:

• lie entirely in the left subtree,
• lie entirely in the right subtree,
• or pass through the current node (taking both left and right branches).

To solve this, we need to consider two things for each node:

1. Best path sum passing through this node (potential candidate for global maximum).
   • This is leftPathSum + node.val + rightPathSum.
   • It means: take the best contribution from the left, the best contribution from the right, and include the current node.
2. Best path sum going downward from this node (to return to parent).
   • Since we can only extend in one direction upwards, we take the larger of left or right plus the node value:
   • max(leftPathSum, rightPathSum) + node.val.

Key trick:

• If a subtree gives a negative sum, we ignore it by treating it as 0, because adding it would only decrease the total.

We keep a global variable maxi to store the maximum path sum encountered so far.

Code Implementation

class Solution:
    maxi = float("-inf")

    def findMaxPathSum(self, root):
        if not root:
            return 0

        # Recursively get max path sums from left and right children
        leftPathSum = self.findMaxPathSum(root.left)
        rightPathSum = self.findMaxPathSum(root.right)

        # If a path contributes negatively, ignore it
        if leftPathSum < 0:
            leftPathSum = 0
        if rightPathSum < 0:
            rightPathSum = 0

        # Update global maximum: best path that passes through this node
        self.maxi = max(self.maxi, leftPathSum + root.val + rightPathSum)

        # Return best single-branch path sum to parent
        return max(leftPathSum, rightPathSum) + root.val

    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.findMaxPathSum(root)
        return self.maxi

Code Explanation

1. Global variable maxi: Keeps track of the maximum path sum found so far. Initialized to negative infinity to handle trees with all negative values.
2. Recursive function findMaxPathSum(root):
   • Base case: If the node is None, return 0.
   • Recursive calls: Compute path sums from left and right children.
   • Negative pruning: If either path sum is negative, set it to 0 (ignore that side).
   • Update maxi: Check if the current path left + node + right is greater than the previous best.
   • Return upward: Pass only one branch (node + max(left, right)) to the parent, because you cannot pass both sides upward.
3. Main function maxPathSum(root):
   • Calls the helper function on the root.
   • Returns the global maximum path sum found.

Time and Space Complexity

• Time Complexity:
  Each node is visited once, and at each node we do constant work.
  So time complexity is O(N), where N is the number of nodes.
• Space Complexity:
  The recursion stack depth is equal to the height of the tree.
  • For a balanced tree: O(log N).
  • For a skewed tree: O(N).

So worst-case space complexity is O(N).

Dry Run Example

Consider [-10, 9, 20, null, null, 15, 7]:

        -10
        /  \
       9    20
           /  \
          15   7

• Start at 15: left = 0, right = 0, current = 15 → update maxi = 15. Return 15.
• At 7: left = 0, right = 0, current = 7 → maxi = 15 (still). Return 7.
• At 20: left = 15, right = 7 → current path = 15 + 20 + 7 = 42 → update maxi = 42. Return 20 + max(15, 7) = 35.
• At 9: left = 0, right = 0, current = 9 → maxi still 42. Return 9.
• At -10: left = 9, right = 35 → current path = 9 + (-10) + 35 = 34 → maxi remains 42. Return upward -10 + max(9, 35) = 25.

Final answer: 42.

Conclusion

The Binary Tree Maximum Path Sum problem requires tracking two types of values at each node:

• The best complete path through the node (both sides + node value).
• The best path to return upward (one side + node value).

By pruning negative sums and maintaining a global maximum, we achieve an efficient O(N) solution.

This is a classic tree DP problem and an excellent example of combining local recursion with a global state to solve a complex optimization problem.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.