Difficulty: HardTrees

Binary Tree Maximum Path Sum

Problem in Plain English

A path is any connected sequence of nodes where none repeats. Given the root of a binary tree with possibly negative values, return the largest sum over all non-empty paths, which need not pass through the root.

Problem Statement

A path in a binary tree is a sequence of nodes where each pair of consecutive nodes is joined by an edge, and no node repeats.

Given the root of a binary tree, return the maximum sum over all non-empty paths. The best path may start and end anywhere and does not need to pass through the root.

Constraints

The number of nodes in the tree is in the range [1, 30000].
-1000 <= Node.val <= 1000

Examples

Example 1

Input: root = [-10,9,20,null,null,15,7]
Output: 42

The best path is 15 -> 20 -> 7. Including the root would produce at most 34, so a path entirely below the root wins.

Example 2

Input: root = [-3]
Output: -3

The path must contain a node. The only valid choice is -3; an empty path with sum zero is not allowed.

Example 3

Input: root = [-8,-3,-5]
Output: -3

Every extra node makes a path worse. Choose the least negative single node, -3, rather than clamping the final answer to zero.

Example 4

Input: root = [1,2,3]
Output: 6

Both child branches help: the path 2 -> 1 -> 3 sums to 6. The downward gain from root is only 4, illustrating why returning the root gain alone loses the answer.

Example 5

Input: root = [5,4,null,3,2]
Output: 12

The left child has a complete two-branch path of sum 9, but only its gain 7 can extend to 5. The legal winning path is 3 -> 4 -> 5, sum 12; adding both grandchildren and 5 would create an illegal fork.

Intuition

A path can rise toward the root and then descend, but it cannot fork into three branches. Call its highest node the peak. At a peak, combine the node value with the best useful downward path from each child; a negative child contribution is better omitted. In Example 1, peak 20 combines 15 and 7 for 42. Its parent can extend only one of those branches, so 20 offers a gain of 35, not 42. This difference between a complete path and an extendable gain is the central invariant.

Approaches

Peak at Every Node

Solution Details

Reveal Peak at Every Node: intuition, complexity, and code

Intuition

Test every node as the peak of a complete path, independently searching each child subtree for its best downward sum. A stack carries a running sum from that child to each descendant; the greatest positive prefix is the useful gain. Example 1 rescans 20, 15 and 7 when evaluating -10, then scans 15 and 7 again when evaluating 20. This deliberate repetition makes the quadratic bottleneck visible without depending on the language call stack.

Step-by-Step Logic

Initialize best below every valid path sum and put the root on the peaks stack. For each popped peak, independently search downward from each child, recording node and sum pairs. In Example 1, the first peak is -10.
For each child search, start gain at zero and add each visited child value to the running sum. The search below 9 yields 9; below 20 it visits sums 20, 35 and 27, so the gains at -10 are 9 and 35.
Combine peak value and both gains, updating best. For -10 the candidate is 34. Push right then left children so peaks are visited left first; peak 9 offers candidate 9 and leaves best at 34.
Repeat independent child searches for each next peak. Peak 20 combines gains 15 and 7 into 42; peaks 15 and 7 cannot improve it.
Return best when the peaks stack empties. Example 1 returns 42. All stacks store references to existing nodes and do not alter the tree.

Why It Works

Every non-empty simple path has one highest node, its peak, and consists of that node plus at most one downward branch in each child subtree. For a fixed child, the explicit search visits every possible downward endpoint and accumulates exactly the nodes between child and endpoint. Its maximum starts at zero so omitting an unhelpful child is allowed. The two subtrees are disjoint, so joining their best gains through the peak yields a legal path and maximizes the sum among paths with that peak. Evaluating every peak covers every path. Initializing best below all possible sums keeps negative single-node paths eligible; every candidate still includes its peak.

Dry Run

Peak at Every Node: variable states at each step
Event	Search stack after event (bottom to top; node,sum)	Gain change	Peaks after event (bottom to top)	Candidate	Best change
Pop peak -10; search left starts	(9,0)	0	empty	pending	-infinity
Pop 9; sum = 0 + 9	empty	0 -> 9	empty	pending	-infinity
Search right starts	(20,0)	reset to 0	empty	pending	-infinity
Pop 20; sum = 0 + 20; push 7 then 15	(7,20), (15,20)	0 -> 20	empty	pending	-infinity
Pop 15; sum = 20 + 15	(7,20)	20 -> 35	empty	pending	-infinity
Pop 7; sum = 20 + 7	empty	35 -> 35	empty	pending	-infinity
Finish peak -10; push 20 then 9	empty	left 9; right 35	20, 9	-10 + 9 + 35 = 34	-infinity -> 34
Pop peak 9; both child searches empty	empty	left 0; right 0	20	9	34 -> 34
Pop peak 20; left search visits (15,0), sum 15	empty	0 -> 15	empty	pending	34
Right search visits (7,0), sum 7	empty	0 -> 7	empty	pending	34
Finish peak 20; push 7 then 15	empty	left 15; right 7	7, 15	20 + 15 + 7 = 42	34 -> 42
Pop peak 15; both searches empty	empty	left 0; right 0	7	15	42 -> 42
Pop peak 7; both searches empty	empty	left 0; right 0	empty	7	42 -> 42
Return best	empty	finished	empty	return 42	42

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(h)

Let n be the node count and h the tree height. Each peak rescans its strict descendants; a chain performs exactly n(n - 1)/2 descendant visits plus n peak visits, giving quadratic worst-case time (a balanced tree takes O(n log n)). The peaks stack and the currently active child-search stack each hold at most O(h) references or node/sum entries; child searches run sequentially. Total temporary entry allocations across all searches can be quadratic, but at most O(h) are live at once. The returned scalar uses constant space. Explicit stacks support height 30000 without recursive calls. Sums have magnitude at most 30000000, fitting Java int and exact JavaScript integers.

Code

Solution.java

1import java.util.ArrayDeque;2import java.util.Deque;3
4class TreeNode {5    int val;6    TreeNode left, right;7    TreeNode(int val) { this.val = val; }8    TreeNode(int val, TreeNode left, TreeNode right) {9        this.val = val; this.left = left; this.right = right;10    }11}12
13class Solution {14    private static class Entry {15        TreeNode node;16        int sum;17        Entry(TreeNode node, int sum) { this.node = node; this.sum = sum; }18    }19
20    private int maxGain(TreeNode root) {21        if (root == null) return 0;22        int gain = 0;23        Deque<Entry> stack = new ArrayDeque<>();24        stack.push(new Entry(root, 0));25        while (!stack.isEmpty()) {26            Entry entry = stack.pop();27            int sum = entry.sum + entry.node.val;28            // Zero permits omitting this entire branch; negative prefixes still29            // need exploration because later positive nodes may outweigh them.30            gain = Math.max(gain, sum);31            if (entry.node.right != null) stack.push(new Entry(entry.node.right, sum));32            if (entry.node.left != null) stack.push(new Entry(entry.node.left, sum));33        }34        return gain;35    }36
37    public int maxPathSum(TreeNode root) {38        int best = Integer.MIN_VALUE;39        Deque<TreeNode> peaks = new ArrayDeque<>();40        peaks.push(root);41        while (!peaks.isEmpty()) {42            TreeNode node = peaks.pop();43            int left = maxGain(node.left), right = maxGain(node.right);44            // Both branches may meet here, but the peak itself is mandatory.45            best = Math.max(best, node.val + left + right);46            if (node.right != null) peaks.push(node.right);47            if (node.left != null) peaks.push(node.left);48        }49        return best;50    }51}

Hints

Hint 1

Split the problem per node: the best path through it versus the best downward path it offers its parent.

Hint 2

A downward path that sums below zero should contribute 0, since skipping it always scores higher.

Hint 3

The arc through a node uses both children, but the value returned upward may extend through only one.

Edge Cases

All values negative: every child gain may be discarded, but each candidate includes its peak, so the largest node value wins.
A single node: the only non-empty path is that node, even when its value is negative or zero.
A best path below the root: Example 1 returns 42 even though the root gain is 25 and its complete candidate is 34.
A fork below a parent: [5,4,null,3,2] must return 12, not the illegal sum 14 of all four nodes.
A negative prefix followed by positive descendants: a child search must keep exploring, since a later value can recover that loss.
A chain of 30000 nodes: explicit stacks avoid recursion limits; the repeated-search baseline still takes quadratic time.

Common Mistakes and Interview Tips

Returning a two-sided candidate to the parent, creating a fork instead of a simple path.
Returning the root downward gain as the answer, missing paths with two branches or paths entirely below the root.
Initializing best to zero or allowing an empty final path, which breaks all-negative trees.
Pruning a negative intermediate running sum during a downward search, even though positive descendants can make that branch useful.
Keying the gain map by node value instead of node identity; repeated values belong to distinct subtrees.
Leaving best in persistent instance state without resetting it, so a second call can reuse the previous answer.
Claiming logarithmic or constant space for the one-pass code: its map keeps every node gain even when the tree is balanced.

Key Takeaway

For tree path problems, distinguish the complete candidate that may use both children from the extendable gain that may use only one. Evaluate the candidate at every node, then use postorder to compute gains once and reuse them above. Explicit traversal stacks preserve this invariant without recursion depth limits.