Binary Tree Maximum Path Sum
Problem
root
of a binary tree, return the largest sum of node values over all non-empty
paths.[1,2,3]Output6 (2→1→3)[-10,9,20,null,null,15,7]Output42 (15→20→7)[-3]Output-31 ≤ n ≤ 3·104 · -1000 ≤ Node.val ≤ 1000
Try it yourself
class Solution {
public int maxPathSum(TreeNode root) {
}
}
val + leftGain + rightGain.
But a parent can extend only one branch, so return val + max(leftGain,
rightGain) upward — and drop any branch whose gain is negative.Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.
Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.
Open the Tree DFS guide →Approaches
Brute ForceRecompute Gains at Every Node
O(n²)Space O(h)Try every node as the path's top: its best path is
val + max(0, gain(left)) + max(0, gain(right)), where
gain = best downward one-branch sum, computed by a fresh DFS. Take the
max over all nodes. Gains of deep nodes are recomputed by every ancestor.
public int maxPathSum(TreeNode root) { if (root == null) return Integer.MIN_VALUE; int through = root.val + Math.max(0, gain(root.left)) + Math.max(0, gain(root.right)); return Math.max(through, Math.max(maxPathSum(root.left), maxPathSum(root.right))); } private int gain(TreeNode node) { // best sum of a path going down from node if (node == null) return 0; return node.val + Math.max(0, Math.max(gain(node.left), gain(node.right))); }
Correct by definition, but O(n²) on a skewed tree.
BetterMemoized Gains (HashMap)
O(n)Space O(n)Same top-node enumeration, but cache gain(node) in a
HashMap. Each node's gain is computed once, so the total work becomes
linear.
private final Map<TreeNode, Integer> memo = new HashMap<>(); public int maxPathSum(TreeNode root) { if (root == null) return Integer.MIN_VALUE; int through = root.val + Math.max(0, gain(root.left)) + Math.max(0, gain(root.right)); return Math.max(through, Math.max(maxPathSum(root.left), maxPathSum(root.right))); } private int gain(TreeNode node) { if (node == null) return 0; Integer cached = memo.get(node); if (cached != null) return cached; int g = node.val + Math.max(0, Math.max(gain(node.left), gain(node.right))); memo.put(node, g); return g; }
Linear time, at the cost of an n-entry map.
OptimalSingle Post-Order Pass + Global Max
O(n)Space O(h)One DFS does both jobs: it records the bent path
val + leftGain + rightGain in maxSum, and returns
the straight path val + max(leftGain, rightGain) to the parent.
Negative gains are clamped to 0 (just don't take that branch).
private int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return maxSum; } private int maxGain(TreeNode node) { if (node == null) return 0; int leftGain = Math.max(maxGain(node.left), 0); // skip negative branches int rightGain = Math.max(maxGain(node.right), 0); maxSum = Math.max(maxSum, node.val + leftGain + rightGain); // path bends here return node.val + Math.max(leftGain, rightGain); // parent extends one side }
One visit per node, only the recursion stack — the standard solution.
maxSum to Integer.MIN_VALUE, not 0 —
an all-negative tree must return its largest single value.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Recompute Gains at Every Node | O(n²) | O(h) |
| Better | Memoized Gains (HashMap) | O(n) | O(n) |
| Optimal | Single Post-Order Pass + Global Max | O(n) | O(h) |
- Returning
val + left + rightto the parent — a path cannot fork. - Starting the answer at 0 — fails for trees with only negative values.
- Not clamping child gains at 0 — forces a negative branch into the path.
- Separate the two quantities out loud: best path here vs best gain for parent.
- Walk through
[-10,9,20,null,null,15,7]to show the path skipping the root. - Point out it is Diameter of Binary Tree with sums instead of lengths.