L17. Maximum Path Sum in Binary Tree

1. Problem Statement & Definition of a Path

Finding the maximum path sum in any given binary tree is a classic algorithmic challenge that tests tree traversal and recursive optimization techniques.

• What is a path? A path is defined as any sequence of nodes where each node appears at most once, starting from any node $A$ and ending at any node $B$.
• Traversal Restriction: You can move only between parent and child nodes. You cannot revisit nodes, nor can you "turn back" in an invalid zig-zag that violates the tree's hierarchical structure.
• Objective: Traverse all possible paths within the binary tree, calculate the sum of node values for each path, and return the maximum possible sum.

2. Why Do We Need This? (Limitations of Brute Force)

Before arriving at an optimal recursive solution, it is vital to evaluate the naive approach to understand why it fails for large trees.

• Brute Force Strategy: Try every possible pair of nodes $(A, B)$ across the tree, trace the unique path between them, and sum their values.
• Time Complexity Pitfall: With $N$ nodes, trying all pairs results in an $O(N^2)$ node combinations. Furthermore, finding the distance and path between arbitrary nodes repeatedly escalates the computational overhead.
• The Optimal Shift: Instead of independent pair searches, we can leverage post-order traversal patterns similar to those used in finding the maximum height or maximum width of a binary tree. This evaluates all potential paths in a single pass of $O(N)$ time.

3. Core Mental Model: The "Umbrella" Path Concept

To evaluate every possible path efficiently, imagine standing at any arbitrary node in the binary tree and treating that node as the "highest point" (or peak) of an umbrella-shaped path.

Real-Life Analogy

Mental Hook: Think of an electrical junction box (the current node) receiving power lines from two separate sub-stations (left subtree and right subtree). To calculate the peak voltage surge flowing through this junction box, you must measure the maximum capacity coming up from the left line, the maximum capacity coming up from the right line, and add them to the local generator's output.

For any given node, a valid path passing through it can be visualized as:

       [Current Node (val)]
            /        \
           /          \
    [Max Left Path]  [Max Right Path]

• Umbrella Formula (Path through current node):

• By applying this formula across every single node in the tree during recursion, we capture every possible "turning point" where a path goes up the left subtree, passes through the root, and goes down the right subtree.

4. Handling Negative Node Values (The Edge Case)

A critical complication arises when subtrees return negative path sums.

• The Problem: If a left subtree yields a path sum of $-30$, adding it would actively decrease our total sum.
• The Fix: We must treat negative sums as weights we refuse to carry. If a recursive call returns a negative value, we replace it with 0.
• Implementation Rule:

By clamping negative returns to zero, we automatically ignore detrimental branches and maximize our potential path sums.

5. Step-by-Step Dry Run Walkthrough

Consider a sample binary tree:

       -10
       /  \
      9    20
          /  \
         15   7

1. Start at Root (-10):
   • We explore its left child (9).
2. At Node 9:
   • Left child is null $\rightarrow$ returns 0.
   • Right child is null $\rightarrow$ returns 0.
   • Umbrella calculation: 9 + 0 + 0 = 9.
   • maxi (global maximum) is updated to 9.
   • Return value sent up to parent (-10): node.val + max(left, right) $\rightarrow$ 9 + max(0, 0) = 9.
3. Back to Root (-10), exploring Right Subtree (20):
   • Move to left child of 20, which is 15.
4. At Node 15:
   • Both children are null $\rightarrow$ returns 0 and 0.
   • Umbrella calculation: 15 + 0 + 0 = 15.
   • maxi updated from 9 to 15.
   • Returns 15 + max(0, 0) = 15 to parent (20).
5. At Node 7 (Right child of 20):
   • Both children are null $\rightarrow$ returns 0 and 0.
   • Umbrella calculation: 7 + 0 + 0 = 7. (maxi remains 15).
   • Returns 7 to parent (20).
6. Back at Node 20:
   • Left sum received = 15.
   • Right sum received = 7.
   • Umbrella calculation: 20 + 15 + 7 = 42.
   • maxi updated to 42 (our ultimate maximum path: 15 -> 20 -> 7).
   • Returns to parent (-10): 20 + max(15, 7) = 20 + 15 = 35.
7. Final Calculation at Root (-10):
   • Left sum = 9, Right sum = 35.
   • Umbrella calculation: -10 + 9 + 35 = 34 (less than 42, so maxi stays 42).

6. Complete Implementation (C++ and Java)

Below are the production-ready implementations in both C++ and Java. Notice how Java handles the global maximum variable via a single-element array to simulate pass-by-reference.

C++ Implementation

class Solution {
private:
    int findMaxPath(TreeNode* node, int& maxi) {
        if (node == nullptr) return 0;

        // Ignore negative path sums by taking max with 0
        int leftSum = max(0, findMaxPath(node->left, maxi));
        int rightSum = max(0, findMaxPath(node->right, maxi));

        // Calculate the maximum path sum with the current node as the peak
        maxi = max(maxi, leftSum + rightSum + node->val);

        // Return the max sum extending to one side for the parent caller
        return node->val + max(leftSum, rightSum);
    }

public:
    int maxPathSum(TreeNode* root) {
        int maxi = INT_MIN;
        findMaxPath(root, maxi);
        return maxi;
    }
};

Java Implementation

class Solution {
    private int findMaxPath(TreeNode node, int[] maxi) {
        if (node == null) return 0;

        // Ignore negative path sums by taking max with 0
        int leftSum = Math.max(0, findMaxPath(node.left, maxi));
        int rightSum = Math.max(0, findMaxPath(node.right, maxi));

        // Calculate the maximum path sum with the current node as the peak
        maxi[0] = Math.max(maxi[0], leftSum + rightSum + node.val);

        // Return the max sum extending to one side for the parent caller
        return node.val + Math.max(leftSum, rightSum);
    }

    public int maxPathSum(TreeNode root) {
        int[] maxi = { Integer.MIN_VALUE };
        findMaxPath(root, maxi);
        return maxi[0];
    }
}

7. Complexity Analysis

Summary and Key Takeaways

• Definition of Path: A valid path connects any node $A$ to any node $B$ in a binary tree without visiting any node twice.
• Suboptimal Brute Force: Comparing all node pairs takes $O(N^2)$ time and is inefficient for hierarchical tree structures.
• The Umbrella Model: Treat every node as the potential peak of a path curving up its left subtree and down its right subtree.
• Formula per Node: Local Max = node.val + max(0, leftSum) + max(0, rightSum).
• Negative Sum Suppression: Always clamp negative recursive returns to 0 to prevent degrading overall path sums.
• Backtracking State Maintenance: Keep track of a running global maximum (maxi) updated at each node during the post-order traversal return phase.
• Single-Side Return Value: A node must return node.val + max(leftSum, rightSum) to its parent so the parent can build a single continuous path upward.
• Optimal Efficiency: Achieves $O(N)$ time complexity and $O(H)$ space complexity, making it an optimal tree dynamic programming pattern.