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 Sam K., 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

More Trees practice problems

See all Trees problems →