Binary Tree Maximum Path Sum

Problem Statement

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes shares a direct edge. Every node appears at most once along the path. The path does not need to pass through the root—it can start and end at any node in the tree.

Given the root of a binary tree, return the maximum sum obtainable from any such path.

Examples

Example 1:

    1
   / \
  2   3

• Path: 2 → 1 → 3
• Maximum path sum: 6

Example 2:

      -10
      /  \
     9    20
         /  \
        15    7

• Path: 15 → 20 → 7
• Maximum path sum: 42

A path can consist of a single node. The values stored in nodes can be negative.

Constraints

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

Why This Problem is Tricky

Four properties make this problem harder than standard tree traversals:

1. The path does not need to pass through the root. Unlike root-to-leaf path problems, the optimal path can live entirely within a subtree.
2. A single node is a valid path. When every value is negative, the answer is the maximum (least negative) node value.
3. A node plays one of two roles. It either acts as the turning point (connecting its left branch, itself, and its right branch into one path) or it acts as a pass-through (contributing itself plus one child branch to its parent’s path).
4. Two quantities must be tracked simultaneously. The value returned to the parent differs from the value used to update the global answer.

Confusing these two roles is the most common source of bugs.

Key Insight: Gain vs. Path Sum

Separate every node’s contribution into two distinct concepts:

1. Max Gain (returned to the parent)

The max gain from a node equals the largest sum achievable by starting at the node and descending through at most one child. The parent consumes this value because a valid path cannot fork twice—once the path forks at the parent, the child’s contribution must be a straight line downward.

$$ \text{gain}(v) = v.\text{val} + \max\bigl(\text{gain}(\text{left}),; \text{gain}(\text{right})\bigr) $$

2. Max Path Sum Through a Node (global update)

The max path sum through a node treats the node as the turning point, joining the left descending branch, the node itself, and the right descending branch into a single path. This path cannot extend upward toward the parent because doing so would require the node to contribute in two directions.

$$ \text{pathSum}(v) = v.\text{val} + \text{leftGain} + \text{rightGain} $$

At each node: update the global maximum with pathSum, but return only gain.

Algorithm

Post-order DFS visits the left subtree, then the right subtree, then processes the current node. This ordering guarantees that both children’s gains are available before the current node needs them.

For every node v:

1. Compute leftGain = max(0, maxGain(v.left)). Clamping to zero discards negative contributions.
2. Compute rightGain = max(0, maxGain(v.right)).
3. Compute pathSum = v.val + leftGain + rightGain. Update the global maximum if pathSum exceeds it.
4. Return v.val + max(leftGain, rightGain) to the caller.

The base case returns 0 for a null node, which naturally integrates with the clamping logic.

Implementation

record TreeNode(int val, TreeNode left, TreeNode right) {
    TreeNode(int val) {
        this(val, null, null);
    }
}

final class BinaryTreeMaxPathSum {

    private int globalMax;

    int maxPathSum(TreeNode root) {
        globalMax = Integer.MIN_VALUE;
        computeGain(root);
        return globalMax;
    }

    /**
     * Returns the maximum "gain" obtainable by starting at {@code node}
     * and descending through at most one child.  As a side effect, updates
     * {@code globalMax} whenever the path through {@code node} (using
     * both children) exceeds the current best.
     */
    private int computeGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // Post-order: solve children first
        int leftGain  = Math.max(0, computeGain(node.left));
        int rightGain = Math.max(0, computeGain(node.right));

        // Path sum treats this node as the turning point
        int pathSum = node.val + leftGain + rightGain;
        globalMax = Math.max(globalMax, pathSum);

        // Return the best single-direction gain to the parent
        return node.val + Math.max(leftGain, rightGain);
    }

    // --- driver -----------------------------------------------------------
    public static void main(String[] args) {
        var solver = new BinaryTreeMaxPathSum();

        // Example 1: [1, 2, 3] → expected 6
        var tree1 = new TreeNode(1,
                new TreeNode(2),
                new TreeNode(3));
        System.out.println(solver.maxPathSum(tree1)); // 6

        // Example 2: [-10, 9, 20, null, null, 15, 7] → expected 42
        var tree2 = new TreeNode(-10,
                new TreeNode(9),
                new TreeNode(20,
                        new TreeNode(15),
                        new TreeNode(7)));
        System.out.println(solver.maxPathSum(tree2)); // 42
    }
}

The globalMax field acts as an accumulator that captures the best turning-point path encountered during the traversal. Using an instance field avoids the common workaround of wrapping an int in a single-element array.

Visual Walkthrough

Trace the algorithm on the second example:

        -10
        /  \
       9    20
           /  \
          15    7

Step	Node	leftGain	rightGain	pathSum	globalMax	Returned Gain
1	9	0	0	9	9	9
2	15	0	0	15	15	15
3	7	0	0	7	15	7
4	20	15	7	42	42	20 + 15 = 35
5	-10	9	35	34	42	-10 + 35 = 25

At node 20 (step 4), the path 15 → 20 → 7 produces a sum of 42, which becomes the global maximum. When control reaches node -10 (step 5), the path through -10 sums to 34, so the global maximum stays at 42. The final answer is 42.

Notice that node -10 returns gain 25 to a hypothetical parent. Although no parent exists here, the logic remains consistent: the gain represents the best straight-line value reachable through -10.

Why Clamping to Zero Works

Clamping each child’s gain to zero with Math.max(0, gain) encodes a powerful decision: if a subtree contributes a negative sum, skip it entirely.

Consider a subtree where every node holds a negative value. The gain propagated upward from that subtree is negative. Including it in the parent’s path sum would decrease the total. By clamping to zero, the algorithm effectively prunes the negative branch, choosing a path that avoids it altogether.

This also handles the “single node” edge case. When both children return negative gains, both are clamped to zero, and pathSum reduces to node.val alone—a valid single-node path.

Complexity Analysis

Time complexity: $O(N)$, where $N$ is the number of nodes. Every node is visited exactly once during the post-order traversal.

Space complexity: $O(H)$, where $H$ is the height of the tree, consumed by the recursion stack.

• Balanced tree: $H = O(\log N)$
• Skewed tree (linked list shape): $H = O(N)$, which risks a StackOverflowError for very deep trees

Edge Cases

Case	Expected Behavior
Single node [5]	Returns 5
All negative values [-3, -2, -1]	Returns -1 (the least negative node)
Left-skewed tree [1, 2, 3, 4] (all left children)	Correctly accumulates along the chain
Right-skewed tree	Same as left-skewed, mirror image
All zeros	Returns 0
Very deep tree (~30,000 nodes, skewed)	Recursion depth concern; iterative approach preferred

Iterative Alternative

An iterative post-order traversal using an explicit stack eliminates the risk of stack overflow on deeply skewed trees. The idea is to simulate the recursion: process each node only after both children have been processed, storing intermediate gains in a hash map.

import java.util.*;

final class BinaryTreeMaxPathSumIterative {

    int maxPathSum(TreeNode root) {
        int globalMax = Integer.MIN_VALUE;
        Map<TreeNode, Integer> gains = new HashMap<>();
        gains.put(null, 0); // base case

        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode current = root;
        TreeNode lastVisited = null;

        while (current != null || !stack.isEmpty()) {
            // Push all left descendants
            while (current != null) {
                stack.push(current);
                current = current.left();
            }

            TreeNode peek = stack.peek();

            // If right child exists and has not been visited, move right
            if (peek.right() != null && peek.right() != lastVisited) {
                current = peek.right();
            } else {
                // Process node in post-order
                stack.pop();
                int leftGain  = Math.max(0, gains.getOrDefault(peek.left(), 0));
                int rightGain = Math.max(0, gains.getOrDefault(peek.right(), 0));

                int pathSum = peek.val() + leftGain + rightGain;
                globalMax = Math.max(globalMax, pathSum);

                gains.put(peek, peek.val() + Math.max(leftGain, rightGain));
                lastVisited = peek;
            }
        }

        return globalMax;
    }
}

The iterative version trades the implicit call stack for an explicit Deque and a HashMap of gains. Time complexity stays $O(N)$; space complexity becomes $O(N)$ due to the hash map, compared to $O(H)$ for the recursive version. Choose the iterative approach when input trees can be arbitrarily deep.

Related Problems

Problem	Connection
Path Sum I, II, III	Simpler variants that fix one or both endpoints of the path (root, leaf), or allow downward-only paths.
Diameter of Binary Tree	Uses the same post-order pattern, but tracks edge count (length) instead of node value sum.
Longest Univalue Path	Same recursive structure—return a single-direction length, track a two-direction answer globally.
Sum Root to Leaf Numbers	Root-to-leaf constraint; no turning-point concept needed.

All four problems share the “return one thing, update another” recursive pattern.

Interviewer Tips

The central insight to articulate: distinguish between the gain (single-direction, returned upward) and the path sum (two-direction, used to update the global answer). Interviewers look for candidates who recognize why the returned value differs from the tracked value.

How to present the solution:

1. Draw the tree. Pick a non-root node and show that the optimal path can live entirely within its subtree.
2. Define gain and path sum explicitly. Write the two formulas on the board.
3. Explain clamping to zero in one sentence: “If a subtree hurts the total, exclude it.”
4. Code the recursive solution. Walk through the example step by step.

Common mistakes to avoid:

• Returning pathSum instead of gain from the recursive call—this produces an invalid forked path.
• Forgetting to clamp negative gains to zero, which causes incorrect results when subtrees are all-negative.
• Initializing globalMax to 0 instead of Integer.MIN_VALUE, which fails when all node values are negative.

Follow-up questions interviewers ask:

• “What if you need to return the actual path nodes, not the sum?” — Store parent pointers or track path indices during traversal; reconstruct the path from the turning-point node.
• “What about the maximum path sum between two leaves specifically?” — The constraint forces both branches to be non-empty at the turning point; adjust the logic to exclude single-node or single-branch paths.
• “How would you handle this on a tree with billions of nodes?” — Use the iterative version to avoid stack overflow, and consider distributed traversal if the tree is stored across multiple machines.