Skip to main content

124. Binary Tree Maximum Path Sum

hardAsked at Pinterest

Binary Tree Maximum Path Sum is Pinterest's signature tree-DP problem: find the maximum sum of any path through any nodes (path need not pass through root). The interviewer wants the classic 'return one side, consider both sides' postorder pattern.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Pinterest loops.

  • Glassdoor (2026-Q1)— Pinterest L4/L5 onsite reports cite Maximum Path Sum as a hard tree-DP round.
  • LeetCode Pinterest tag (2026-Q1)— On the Pinterest company-tagged problem list.

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: Path 2 -> 1 -> 3 sums to 6.

Example 2

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

Explanation: Path 15 -> 20 -> 7 sums to 42.

Approaches

1. Recursive DFS returning best-single-side, updating global best (optimal)

DFS returns the best path sum that starts at this node and goes DOWN one side. At each node, compute the candidate path that splits left + node + right and update the global best.

Time
O(n)
Space
O(h) recursion
function maxPathSum(root) {
  let best = -Infinity;
  function dfs(node) {
    if (!node) return 0;
    const leftGain = Math.max(dfs(node.left), 0);
    const rightGain = Math.max(dfs(node.right), 0);
    const through = node.val + leftGain + rightGain;
    if (through > best) best = through;
    return node.val + Math.max(leftGain, rightGain);
  }
  dfs(root);
  return best;
}

Tradeoff: O(n) single postorder pass. Two key tricks: (1) clamp child contributions to >= 0 (negative paths shouldn't be extended); (2) the function returns the best one-sided extension but UPDATES the global with the through-node path.

Pinterest-specific tips

Pinterest interviewers care most about the 'return one side, consider both' distinction. Narrate it: 'this function returns the best EXTENSION to a parent — necessarily one-sided. The through-node candidate splits left + right at this node and updates a global maximum.' Skipping that distinction is the #1 reason candidates write subtly wrong code. Initialize best = -Infinity so all-negative trees return the largest single negative.

Common mistakes

  • Returning the through-node candidate instead of the one-sided extension — the parent can't use a split path.
  • Not clamping negative gains to 0 — including a negative subtree only hurts.
  • Initializing best = 0 — fails on all-negative trees like [-3].
  • Forgetting to handle a single-node tree — the answer is just node.val if both children are null.

Follow-up questions

An interviewer at Pinterest may pivot to one of these next:

  • Return the actual path nodes, not just the sum.
  • Maximum Average Subtree.
  • K-ary tree variant — multiple children, only the two best contribute.
  • Diameter of Binary Tree (LeetCode 543) — same pattern, edge counts instead of sums.

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 the recursive return value differ from the global best?

The parent can only use a one-sided extension (otherwise the path would visit a node twice). But at the current node, the through-node combination is a valid standalone path candidate, so we track it globally.

Why does Pinterest like this problem specifically?

It tests the 'return one thing, update another' tree-DP pattern that shows up across Pinterest's tree-shaped data (board hierarchies, comment threads, pin lineage). Mastering this unlocks dozens of follow-ups.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →