hard Path with Maximum Sum

Problem Statement

Find the path with the maximum sum in a given binary tree. Write a function that returns the maximum sum.

A path can be defined as a sequence of nodes between any two nodes and doesn’t necessarily pass through the root. The path must contain at least one node.

Constraints:

• The number of nodes in the tree is in the range [1, 3 * 10⁴].
• -1000 <= Node.val <= 1000

Solution

This problem follows the Binary Tree Path Sum pattern and shares the algorithmic logic with Tree Diameter. We can follow the same DFS approach. The only difference will be to ignore the paths with negative sums. Since we need to find the overall maximum sum, we should ignore any path which has an overall negative sum.

Here is the visual representation of the algorithm:

Code

Here is the code for this algorithm:

// class TreeNode {
//   int val;
//   TreeNode left;
//   TreeNode right;

//   TreeNode(int x) {
//     val = x;
//   }
// };

class Solution {

  private static int globalMaximumSum;

  public int findMaximumPathSum(TreeNode root) {
    globalMaximumSum = Integer.MIN_VALUE;
    findMaximumPathSumRecursive(root);
    return globalMaximumSum;
  }

  private static int findMaximumPathSumRecursive(TreeNode currentNode) {
    if (currentNode == null) return 0;

    int maxPathSumFromLeft = findMaximumPathSumRecursive(currentNode.left);
    int maxPathSumFromRight = findMaximumPathSumRecursive(currentNode.right);

    // ignore paths with negative sums, since we need to find the maximum sum we should
    // ignore any path which has an overall negative sum.
    maxPathSumFromLeft = Math.max(maxPathSumFromLeft, 0);
    maxPathSumFromRight = Math.max(maxPathSumFromRight, 0);

    // maximum path sum at the current node will be equal to the sum from the left
    // subtree + the sum from right subtree + val of current node
    int localMaximumSum =
      maxPathSumFromLeft + maxPathSumFromRight + currentNode.val;

    // update the global maximum sum
    globalMaximumSum = Math.max(globalMaximumSum, localMaximumSum);

    // maximum sum of any path from the current node will be equal to the maximum of
    // the sums from left or right subtrees plus the value of the current node
    return Math.max(maxPathSumFromLeft, maxPathSumFromRight) + currentNode.val;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    System.out.println("Maximum Path Sum: " + sol.findMaximumPathSum(root));

    root.left.left = new TreeNode(1);
    root.left.right = new TreeNode(3);
    root.right.left = new TreeNode(5);
    root.right.right = new TreeNode(6);
    root.right.left.left = new TreeNode(7);
    root.right.left.right = new TreeNode(8);
    root.right.right.left = new TreeNode(9);
    System.out.println("Maximum Path Sum: " + sol.findMaximumPathSum(root));

    root = new TreeNode(-1);
    root.left = new TreeNode(-3);
    System.out.println("Maximum Path Sum: " + sol.findMaximumPathSum(root));
  }
}

Time Complexity

The time complexity of the above algorithm is , where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once.

Space Complexity

The space complexity of the above algorithm will be in the worst case. This space will be used to store the recursion stack. The worst case will happen when the given tree is a linked list (i.e., every node has only one child).

🎯 STRICT STANDOUT — Solution Path with Maximum Sum

1. Why / judgment

Any-node path (LC 124 family) = diameter skeleton with values: return best one arm upward; update global with left_arm+right_arm+val. Clamp arms with max(0,·) so negatives never extend.

2. Worked complexity / trace (K11)

Visit each node once → Θ(n) time, Θ(h) stack.
Tree [1,2,3]: arms 2,3; through root 1+2+3=6; return max(2,3)+1=4.
All-negative e.g. [-3,-2,-1]: clamp makes arms 0; global tracks best single node −1.
Init global = MIN_VALUE so single negative node wins.

3. Pattern + when-NOT (K12)

Name: MAX PATH SUM (post-order dual-role)

Recognition: path any two nodes; maximize sum; may not pass root.

When-NOT: Root-to-leaf only → no both-arms global. Diameter of unweighted edges → height not values. Undirected graph path → different algo.

4. Edge hand-run (K13)

single node → that val.
null children return 0 then clamp.
skewed chain: best subarray-like along tree path.

5. Interviewer follow-ups

Q1. Why return one arm not both?
A: Parent can only extend one chain; bend is recorded in global only.

Q2. Why clamp?
A: Negative arm never helps any extension; node alone still competes via global.

Q3. Same as diameter?
A: Same skeleton; diameter uses heights, this uses clamped path sums.