Path with Maximum Sum (Maximum Sum of Any Path Between Two Nodes)

• Post-order traversal – process children first, then the current node, so child gains are known before the node decides.
• Single branch return – to the parent, offer node.value + max(leftGain, rightGain), the best straight extension.
• Bent path update – update the global max with node.value + leftGain + rightGain, the best path bending through this node.
• Zero clamp – Math.max(0, childGain) ignores branches that would lower the sum.
• Initialization – seed globalMax = Integer.MIN_VALUE so a tree of all negatives returns the least-negative single node.

What is the problem?

Find the maximum sum over any connected path in a binary tree. A path is a sequence of connected nodes, and it need not pass through the root or touch a leaf. Node values may be negative.

How does the post-order approach work?

• Each node plays two roles:
• To its parent it offers a straight downward extension: node.value + max(leftGain, rightGain).
• Internally, it considers a path that bends through itself using both children: node.value + leftGain + rightGain.

The bent path cannot be extended further upward (it already uses both branches), so it only updates the global max, not the return value.

package com.bank.service;

public class MaxPathSumFinder {

    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    private static int globalMax;

    public static int maxPathSum(TreeNode root) {
        globalMax = Integer.MIN_VALUE;
        dfs(root);
        return globalMax;
    }

    private static int dfs(TreeNode node) {
        if (node == null) return 0;

        int leftGain = Math.max(0, dfs(node.left));   // clamp at 0
        int rightGain = Math.max(0, dfs(node.right));  // clamp at 0

        // Bent path through this node
        int bentPath = node.val + leftGain + rightGain;
        globalMax = Math.max(globalMax, bentPath);

        // Return single branch to parent
        return node.val + Math.max(leftGain, rightGain);
    }

    public static void main(String[] args) {
        // Profit/loss desks at National Bank of India
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(2);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(20);
        root.left.right = new TreeNode(1);
        root.right.right = new TreeNode(-25);
        root.right.right.left = new TreeNode(3);
        root.right.right.right = new TreeNode(4);

        System.out.println("Maximum path sum: " + maxPathSum(root));
    }
}

Maximum path sum: 42

The best path is 20 - 2 - 10 - 10 = 42 (going up from 20 through 2 to root 10, then down to right child 10).

Why clamp at zero?

If extending into a child would lower the sum, the optimal path simply stops at the current node. Math.max(0, childGain) handles this: a negative gain becomes zero, meaning that branch is not used.

// Without clamping: path forced to include losing branches
int leftGain = dfs(node.left); // might be -50, dragging sum down

// With clamping: losing branches ignored
int leftGain = Math.max(0, dfs(node.left)); // -50 becomes 0

Why initialize globalMax to Integer.MIN_VALUE?

A tree of all-negative values has a maximum path equal to the single least-negative node. If you seed globalMax at zero, you would wrongly return zero even though zero is not a valid path sum (no such path exists).

// Wrong: seed at 0
int globalMax = 0; // returns 0 for tree [-3, -5, -1]

// Correct: seed at MIN_VALUE
int globalMax = Integer.MIN_VALUE; // returns -1 for tree [-3, -5, -1]

What is the asymmetry between return and update?

This is the most common bug. The return value to the parent is a single branch (can only extend one way). The global update uses both branches (bends through the node). Confusing the two causes wrong answers.

| | Return to parent | Global update |
|---|---|---|
| Formula | node + max(left, right) | node + left + right |
| Can extend? | Yes, parent adds more | No, already uses both branches |
| Purpose | offer best extension | record best complete path |

What are edge cases?

• Single node: the answer is that node's value.
• All negative: the answer is the least-negative single node.
• Perfect tree of positive values: the best path goes through the root using both subtrees.

What should a senior engineer know?

For monetary values in a profit-and-loss tree at National Bank of India, use BigDecimal to avoid overflow and clamp losses at BigDecimal.ZERO. The global max is seeded at a very large negative BigDecimal. The pattern generalizes to any tree problem where you need the best connected substructure.

What are common interview follow-up questions?

• How would you return the actual path, not just the sum?
• What if the path must include the root?
• Can you solve this iteratively with an explicit stack?