Skip to main content

124. Binary Tree Maximum Path Sum

hardAsked at Netflix

Given 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 Alex Chen, 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

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

Explanation: The optimal path is 2 -> 1 -> 3 with sum = 2 + 1 + 3 = 6.

Example 2

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

Explanation: 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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Binary Tree Maximum Path Sum and other Netflix interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →