← DSA Atlas
Dedicated problem page · #124

Binary Tree Maximum Path Sum

HardTrees and Binary Search TreesPost-order gain with global bestRecursive tree DP (post-order DFS)
Solve on LeetCode ↗
124
HardTrees and Binary Search TreesRecursive tree DP (post-order DFS)Post-order gain with global best

Binary Tree Maximum Path Sum

Given the root of a binary tree, a path is any sequence of nodes connected by parent-child edges, where each node appears at most once and the path need not pass through the root. Return the maximum sum of node values along any such path.

Open official problem prompt ↗
In plain English

Find the largest possible sum of values on any connected path in the tree, where the path may start and end at any nodes and does not have to touch the root.

Picture it like this

Imagine each node is a junction on a hiking trail with an elevation reward. At a junction you may combine the best downhill trail on the left with the best on the right to enjoy the whole view (recorded as the answer), but when you report a route to the junction above you, you can only hand off one downhill branch — you cannot walk two ways at once.

Example
Input
root = [-10, 9, 20, null, null, 15, 7]
Output
42
Why
The best path is 15 -> 20 -> 7 with sum 15 + 20 + 7 = 42.
Constraints
The number of nodes is in the range [1, 3 * 10^4]-1000 <= Node.val <= 1000
Pattern lesson

See the pattern, then code

Post-order gain with global best
Recognition clue

You need the best path that can bend at a node (go down-left and down-right) but a node can only extend one branch upward to its parent — that split between what you return and what you record is the tell.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. For each node compute the maximum downward gain of a single branch. The best path THROUGH a node is node.val + left_gain + right_gain, but the value you hand back to the parent can only include one branch, because a path cannot fork twice.

New words, made simpleKnow these before the algorithm
Path
A sequence of nodes joined by edges with no node repeated; it can bend at exactly one node.
Single-branch gain
The best sum obtainable starting at a node and going straight down through one child only.
Post-order
Visiting both children before the node itself, so children's answers are ready when the node is processed.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Try every pair of nodes

Recomputing overlapping paths is far too slow for 30k nodes.

For each pair of nodes compute the path sum between them.

Time O(n^2) or worseSpace O(h)
Best choicePost-order gain with global maximum

One traversal, each node visited once — clean and optimal.

Each node returns its best single downward branch; separately record the bent path node.val + left + right as a candidate answer.

Time O(n)Space O(h)
The rule we keep true

Invariant

When gain(node) returns, `best` already reflects the maximum path whose highest (bend) point is node or any node in its subtree.

Why this is correct

Reasoning

Every path has a unique topmost node where it bends. At that node the path equals node.val + (best left branch, or 0) + (best right branch, or 0). Because we evaluate this bent expression at every node, and every path bends at some node, the global maximum over all nodes is the answer. Returning only one branch upward respects the no-fork rule for the parent's path.

The algorithm in three movesSay these aloud before coding
1Recurse post-order to get each child's max single-branch gain

gain(15)=15, gain(7)=7

2Clamp negative gains to 0 so harmful branches are dropped

at 20: best=max(best,20+15+7)=42

3Update a global best with node.val + left + right (the bent path)

gain(20) returned to root = 20+15 = 35

4Return node.val + max(left, right) to the parent (one branch only)

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
-100
91
202
153
74
1 · Readnode 15
2 · Askbest branch to return?
3 · Update statebest = 15
4 · Resultreturns 15
Key takeaway

The bent path 15-20-7 sums to 42 while node 20 returns only 35 upward.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 5-7Null base case

    An empty child contributes zero gain so paths simply skip it.

  2. 2
    Lines 8-9Clamp children to zero

    A negative branch would only shrink the sum, so we treat it as 0 (i.e., don't extend into it).

  3. 3
    Lines 10Record the bent path

    node.val + left + right is the best path bending at this node; compare it to the running best.

  4. 4
    Lines 11Return one branch

    The parent can only continue through a single child, so we hand back node.val plus the larger branch.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single node tree returns that node's value
  • All-negative values — the answer is the least-negative single node, which works because we compare node.val itself
  • Deep skewed tree stresses recursion depth (O(h) stack)
!

Common beginner mistakes

  • Returning node.val + left + right upward (illegal fork) instead of node.val + max(left,right)
  • Initializing best to 0, which breaks all-negative trees — use negative infinity
  • Forgetting to clamp negative child gains to 0
Check your understanding

Why can the value returned to the parent include only one child's gain, while the recorded answer includes both?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#543Diameter of Binary TreePost-order height with a running best#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#236Lowest Common Ancestor of a Binary TreeBottom-up LCA search#105Construct Binary Tree from Preorder and InorderPreorder root + inorder split