Skip to main content

124. Binary Tree Maximum Path Sum

hardAsked at Google

Find the maximum sum path in a binary tree, where the path can start and end at any node. Google asks this to test whether you can separate two concepts at the same recursive node: the best path that 'extends upward' versus the best path that 'turns at this node and goes nowhere else.'

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L4/L5 onsite reports cite this as the tree-recursion hard.
  • Blind (2025-10)— Recurring Google interview problem flagged as challenging due to the dual-return pattern.

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. 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 a path sum of 6.

Example 2

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

Explanation: The optimal path is 15 - 20 - 7 with a path sum of 42.

Approaches

1. Brute-force every (start, end) pair

Enumerate every pair of nodes; for each, compute the path sum via LCA.

Time
O(n^2)
Space
O(n)
// Brute-force outline only — actual implementation requires LCA + path-sum computation per pair.
// Mention but do not code under time pressure.

Tradeoff: Quadratic and forgets the recursive structure. Mention only as the anti-pattern.

2. Single-pass DFS with dual return (optimal)

Recurse. At each node return 'max gain when extending upward' (one child, not both), but separately update a global max with 'turn at this node' (both children).

Time
O(n)
Space
O(h) recursion stack
function maxPathSum(root) {
  let best = -Infinity;
  function gain(node) {
    if (!node) return 0;
    // best gain when extending upward — at most one child path
    const leftGain = Math.max(gain(node.left), 0);
    const rightGain = Math.max(gain(node.right), 0);
    // turning at this node: combine both children + current value
    const localBest = node.val + leftGain + rightGain;
    best = Math.max(best, localBest);
    // return only the upward-extending value
    return node.val + Math.max(leftGain, rightGain);
  }
  gain(root);
  return best;
}

Tradeoff: Single pass, O(n) time. The trick is separating two concepts: the value RETURNED (used by the parent) is the upward-extending gain; the value SIDE-EFFECTED into best is the turn-at-this-node value.

Google-specific tips

Google interviewers grade this on whether you understand the dual concept: the function RETURNS the best gain when extending to the parent (must pick at most one child), but SIDE-EFFECTS into a global the best 'turn here' value (combines both children). If you try to return both, the recursion gets tangled. Articulate this separation before coding.

Common mistakes

  • Returning the local max instead of the upward gain — breaks the parent's calculation.
  • Forgetting Math.max(gain(child), 0) — without it, negative subtrees drag down sums that shouldn't include them.
  • Initializing best to 0 instead of -Infinity — fails on all-negative trees.

Follow-up questions

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

  • Return the actual path, not just the sum.
  • What if the tree is a DAG instead of a tree?
  • Diameter of Binary Tree (LC 543) uses the same dual-return pattern.

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 two different values — one returned, one side-effected?

A path that 'turns' at a node uses both children and can't extend any higher. A path that 'extends upward' can use only one child because the parent will glue another segment on top. Mixing these confuses the recursion.

Why initialize best to -Infinity?

All node values can be negative (-1000 lower bound). If you init best to 0, you'd return 0 for a tree like [-3] which is wrong — the answer is -3.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →