Skip to main content

124. Binary Tree Maximum Path Sum

hard

Find the largest possible sum of any path through a binary tree — paths can start and end anywhere and bend at most once at any node. The classic 'global vs. local return' interview decomposition.

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

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 a path sum of 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 a path sum of 15 + 20 + 7 = 42.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Two different quantities. What you RETURN from recursion is 'best straight-line path going down through this node' (single side only). What you UPDATE on a global is 'best path that bends at this node' (uses both sides).

Hint 2

At each node: leftGain = max(0, recurse(left)), rightGain = max(0, recurse(right)). Negative contributions are ignored.

Hint 3

Update the global with node.val + leftGain + rightGain. Return node.val + max(leftGain, rightGain) for the parent.

Solution approach

Reveal approach

Post-order DFS with a mutable global. Initialize globalMax = -Infinity. Helper maxGain(node): if node is null, return 0. Compute leftGain = max(0, maxGain(node.left)) and rightGain = max(0, maxGain(node.right)) — clamping at 0 means we skip negative subtrees. Update globalMax = max(globalMax, node.val + leftGain + rightGain) — this is the 'bend at this node' path that uses both sides. Return node.val + max(leftGain, rightGain) — what the parent receives, since the parent can only extend one side. Run maxGain(root), discard the return, and return globalMax. The distinction between 'what I commit globally' and 'what I report to my parent' is the heart of the problem. O(n) time, O(h) recursion space.

Complexity

Time
O(n)
Space
O(h)

Related patterns

  • tree-dfs
  • recursion
  • post-order
  • dynamic-programming

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft
  • Apple
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Binary Tree Maximum Path Sum and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →