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

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Path with Maximum Sum — problem

0. Pattern family

Family: Tree DP — max path any node-to-node (gain clamp); global vs return arm

1. Why / judgment (K3)

Path may bend at any node (left arm + node + right arm) and need not touch root. DFS returns the best downward arm to parent: node.val + max(0, best child arm). At node, candidate global = node.val + max(0,left) + max(0,right). Judgment: clamping negatives is correct for arms, but global must initialize to −∞ / MIN so all-negative trees return the largest (least negative) node — do not clamp the node itself away. Same skeleton as diameter (replace edge counts with sums).

2. Worked complexity / derivation (K11)

One DFS visits each node once → O(n) time.
Space O(h) recursion (O(n) skewed).
Brute all pairs paths exponential/quadratic — reject.

3. Pattern + recognition + when-NOT (K12)

Name: TREE DP BEND PATH — MAX PATH SUM (LC 124 family)

Recognition: binary tree; max sum path any two nodes; node values may be negative.

When-NOT: If path must start at root → simpler root-to-leaf max. If path must be downward only → no bend global. If diameter by edges → same structure count edges not sums. If unrestricted graph → harder.

4. Edge hand-run (K13)

Tree 1,{2,3}: path 2-1-3 sum 6.
Tree −1,{−2,−3}? wait −1 left −2: best single node −1 (global init MIN).
Code sample −1,{−3}: max(−1,−3)=−1.
Edge: single node 5 →5. All negative: answer = max node value.
Hand-run: root=1 L=2 R=3 → arms 2,3 local=6 global=6 return 1+3=4.

5. Interviewer follow-ups & drills

Q1. Why return only one child?
Model answer: Parent path cannot use both arms without double-using node as bend only at this node — parent extends a single chain.

Q2. Why max(0, child)?
Model answer: Negative child arm hurts the chain; drop it. Node alone still considered in global via localMaximumSum with zeros.

Q3. All-negative trap?
Model answer: globalMaximumSum=MIN_VALUE; never start at 0 or you wrongly return 0 for all-negative trees.

✅ Solution 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:

java

// 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

0. Pattern family

Family: Tree DP — max path any node-to-node (gain clamp); global vs return arm

1. Why / judgment (K3)

2. Worked complexity / derivation (K11)

One DFS visits each node once → O(n) time.
Space O(h) recursion (O(n) skewed).
Brute all pairs paths exponential/quadratic — reject.

3. Pattern + recognition + when-NOT (K12)

Name: TREE DP BEND PATH — MAX PATH SUM (LC 124 family)

Recognition: binary tree; max sum path any two nodes; node values may be negative.

4. Edge hand-run (K13)

Tree 1,{2,3}: path 2-1-3 sum 6.
Tree −1,{−2,−3}? wait −1 left −2: best single node −1 (global init MIN).
Code sample −1,{−3}: max(−1,−3)=−1.
Edge: single node 5 →5. All negative: answer = max node value.
Hand-run: root=1 L=2 R=3 → arms 2,3 local=6 global=6 return 1+3=4.

5. Interviewer follow-ups & drills

Q1. Why return only one child?
Model answer: Parent path cannot use both arms without double-using node as bend only at this node — parent extends a single chain.

Q2. Why max(0, child)?
Model answer: Negative child arm hurts the chain; drop it. Node alone still considered in global via localMaximumSum with zeros.

Q3. All-negative trap?
Model answer: globalMaximumSum=MIN_VALUE; never start at 0 or you wrongly return 0 for all-negative trees.

🧩 Pattern · Arrays

Recognize it: Scan once tracking what you need (running max/sum), or precompute a prefix-sum / hash → turn O(n²) into O(n).

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Path with Maximum Sum? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Path with Maximum Sum** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Path with Maximum Sum** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Path with Maximum Sum**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Path with Maximum Sum**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Median of Two Sorted Arrays First Missing Positive →