124. Binary Tree Maximum Path Sum
hardAsked at NetflixGiven a binary tree, find the path with the maximum sum where a path is any sequence of nodes connected by edges (no node repeats). Netflix asks this for the hard slot — the key is separating 'gain to return upward' from 'best path passing through this node'.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Netflix loops.
- Glassdoor (2026-Q1)— Netflix senior IC onsite reports list this as the hardest tree problem in the loop.
- Blind (2025-11)— Netflix L5/L6 writeups specifically call out the 'two return values' (max gain vs global best) as the signal.
Problem
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path.
Constraints
The number of nodes in the tree is in the range [1, 3 * 10^4].-1000 <= Node.val <= 1000
Examples
Example 1
root = [1,2,3]6Explanation: The optimal path is 2 -> 1 -> 3 with sum = 2 + 1 + 3 = 6.
Example 2
root = [-10,9,20,null,null,15,7]42Explanation: The optimal path is 15 -> 20 -> 7 with sum = 15 + 20 + 7 = 42.
Approaches
1. Naive: try every node as a potential bend point
For every node, recursively compute the longest left and right downward paths, then compute the candidate sum = node.val + left + right.
- Time
- O(n^2)
- Space
- O(h)
function maxPathSumNaive(root) {
let best = -Infinity;
function maxDown(node) {
if (!node) return 0;
return Math.max(0, node.val + Math.max(maxDown(node.left), maxDown(node.right)));
}
function walk(node) {
if (!node) return;
const l = maxDown(node.left), r = maxDown(node.right);
best = Math.max(best, node.val + l + r);
walk(node.left); walk(node.right);
}
walk(root);
return best;
}Tradeoff: Conceptually clean (every node could be the 'bend point') but recomputes maxDown for each ancestor — O(n^2). Mention it to motivate the single-pass version.
2. Single-pass DFS returning max-gain-upward (optimal)
Each node returns the max gain (max of 0, node.val + max(left gain, right gain)) to its parent. The 'bend point' candidate is node.val + leftGain + rightGain — compared against a global best.
- Time
- O(n)
- Space
- O(h) recursion
function maxPathSum(root) {
let best = -Infinity;
function gain(node) {
if (!node) return 0;
const l = Math.max(0, gain(node.left));
const r = Math.max(0, gain(node.right));
best = Math.max(best, node.val + l + r);
return node.val + Math.max(l, r);
}
gain(root);
return best;
}Tradeoff: O(n). The two-return-value pattern: gain() returns 'what I can offer my parent' (a single downward path); best is updated with 'the bend-point sum at this node.' The Math.max(0, gain) clamps negative subtree contributions to zero — never include a subtree that hurts.
Netflix-specific tips
Netflix interviewers explicitly grade whether you can separate the two concepts: 'gain returned to parent' (one downward direction only) and 'best path bending at this node' (both directions combined). Say this out loud BEFORE writing code: 'My recursion returns one value but updates a global with another.' That's the whole problem.
Common mistakes
- Returning node.val + leftGain + rightGain from the recursion — wrong, the parent can only follow ONE of the two children, not both.
- Forgetting the Math.max(0, ...) clamp on subtree gains — including a negative subtree hurts the path.
- Initializing best = 0 instead of -Infinity — fails on all-negative trees.
Follow-up questions
An interviewer at Netflix may pivot to one of these next:
- What if path could include both directions through any node? (Same problem.)
- Longest path between any two nodes (not weighted by val) — Diameter of Binary Tree (LC 543).
- Path Sum III (LC 437) — count paths summing to a target.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does gain return node.val + max(l, r) instead of node.val + l + r?
Because gain() is 'what you can give your parent' — and a parent can only continue down ONE of your subtrees. Returning l + r would imply the parent can fork through you, which violates the no-node-repeats rule.
Why clamp negative gains to zero?
If a subtree's max gain is negative, it's better to just not include it — the empty path contribution is 0. Clamping to 0 in the recursion encodes 'skip this subtree if it would hurt.'
Free learning resources
Curated free links for this problem.