Loading…

hardTreesLC #124Frequently asked

Binary Tree Maximum Path Sum

Q: How do you solve Binary Tree Maximum Path Sum using the Brute Force — Best Path Through Each Node approach?

When to use it: Useful to frame the problem ('every path peaks at some node') before showing how one DFS computes it all in O(n). Start from the observation that *every* path peaks at exactly one node — the unique highest point where it may branch into both subtrees. So the global answer is the maximum, over all nodes, of 'best bending path that peaks at this node'. **Best path peaking at a node.** Define `down(x)` = the largest sum of a straight downward path that starts at `x` and goes toward the leaves, taking 0 if every option is negative. Then the best path peaking at node `p` is `p.val + max(down(p.left), 0) + max(down(p.right), 0)`. Take the max of that across all nodes. **Why it's quadratic.** Computing `down(x)` is itself a recursion over a subtree. If we call it independently for every peak candidate, we recompute the same downward sums over and over — n peaks × O(n) per `down` = O(n²). **Why mention it.** It cleanly establishes the framing ('paths peak at a node; combine two downward arms') that the optimal solution reuses. The leap to O(n) is simply: compute each node's downward gain *once* and fold the peak check into the same traversal. Time complexity: O(n²). Space complexity: O(h).

LCPractice

Trees & BST · 13 of 41 · 10 min

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**.

In plain English

We want the highest-sum path anywhere in the tree, where a path is any connected chain of nodes that visits each at most once and may bend at exactly one node (its highest point). It need not touch the root or reach a leaf. Because values can be negative, we may want to exclude entire branches.

Examples

Example 1

Input: root = [1,2,3]
Output: 6
Note: The path 2 → 1 → 3 bends at the root and sums to 6.

Example 2

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Note: The best path is 15 → 20 → 7 = 42; it bends at 20 and never touches the negative root.

Example 3

Input: root = [-3]
Output: -3
Note: Single node, all negative — the answer is that one node, which is why we start the global max at −∞.

Constraints

The number of nodes is in the range [1, 3 × 10⁴]
-1000 ≤ Node.val ≤ 1000
The path is non-empty (at least one node) and node values may be negative

Clarifying questions4First question: Does the path have to pass through the root or reach a leaf?Explore questions

Q1.Does the path have to pass through the root or reach a leaf?
No. It can start and end anywhere, as long as the nodes form a connected chain. That's why we track a global maximum across all nodes.
Q2.Can node values be negative?
Yes. So we clamp each child's contribution at 0 (skip negative branches) and initialize the answer to −∞, since even the best single node could be negative.
Q3.Can a path bend (go up through a node and back down)?
Yes, but only once — a path peaks at a single node where it may use both children. Above that node it can only continue through one side.
Q4.Is the path non-empty?
Yes, at least one node. With all-negative values the answer is the single largest (least negative) node.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Post-order DFS where each node returns the best single downward gain it can contribute to its parent — `node.val + max(0, leftGain, rightGain)` using only ONE child. Separately, at every node, consider the best path that bends through it (`node.val + leftGain + rightGain`, using BOTH children) and update a global maximum. The two distinct quantities — what you return up vs what you record globally — are the crux. O(n) time, O(h) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can separate two related-but-different values in a single DFS: the best downward extension a node hands to its parent versus the best bending path that completes at that node — and whether you correctly drop negative contributions.

Where candidates slip

Returning `val + left + right` (the split sum) up to the parent, which lets a path use two branches of a node *and* still extend through it — an impossible path. Or initializing the answer to 0 and breaking on all-negative trees.

How to stand out

Articulate the two quantities precisely, justify the max(0, …) clamp, explain why post-order is required, and note the structural identity with Diameter of Binary Tree.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Best Path Through Each Node	`O(n²)`	`O(h)`	Useful to frame the problem ('every path peaks at some node') before showing how one DFS computes it all in O(n).	Read
2	Single Post-Order DFS — Gain Up, Split Recorded (Optimal)Optimal	`O(n)`	`O(h)`	The answer they want. 'One DFS: each node returns its best single-branch gain; I update a global max with the two-branch split.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Two quantities at each node

How to read it:Return one branch upward (so the parent can extend); record the both-branch split as a candidate global best.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Best Path Through Each Node

TimeO(n²)SpaceO(h)

Useful to frame the problem ('every path peaks at some node') before showing how one DFS computes it all in O(n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Every path has a single highest node where it bends. Can you fix that node and ask: what's the best path peaking here?

2Hint 2Explore hint

For a fixed peak node, the best bending path is its value plus the best downward path into the left subtree plus the best downward path into the right subtree (each clamped at 0).

3Hint 3Explore hint

Computing 'best downward path from X' is itself a recursion. Doing it independently for every candidate peak repeats work — that's the O(n²).

A · Core idea

Start from the observation that every path peaks at exactly one node — the unique highest point where it may branch into both subtrees. So the global answer is the maximum, over all nodes, of 'best bending path that peaks at this node'.

Best path peaking at a node. Define down(x) = the largest sum of a straight downward path that starts at x and goes toward the leaves, taking 0 if every option is negative. Then the best path peaking at node p is p.val + max(down(p.left), 0) + max(down(p.right), 0). Take the max of that across all nodes.

Why it's quadratic. Computing down(x) is itself a recursion over a subtree. If we call it independently for every peak candidate, we recompute the same downward sums over and over — n peaks × O(n) per down = O(n²).

Why mention it. It cleanly establishes the framing ('paths peak at a node; combine two downward arms') that the optimal solution reuses. The leap to O(n) is simply: compute each node's downward gain once and fold the peak check into the same traversal.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

peak 9

9 + 0 + 0

Statecandidate = 9

Final result42

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the full code

solution.javaJava

Brute Force — Best Path Through Each Node — reference

3 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
public int maxPathSum(TreeNode root) {
9
    if (root == null) {
10
        return 0;
11
    }
12
    int peakHere = root.val
13
        + Math.max(down(root.left), 0)
14
        + Math.max(down(root.right), 0);
15
    int best = peakHere;
16
    if (root.left != null) best = Math.max(best, maxPathSum(root.left));
17
    if (root.right != null) best = Math.max(best, maxPathSum(root.right));
18
    return best;
19
}
20
 
21
// Best straight downward path starting at node (0 if all negative).
22
private int down(TreeNode node) {
23
    if (node == null) {
24
        return 0;
25
    }
26
    // down(): best straight downward path; recomputed per peak → O(n²).
27
    return node.val + Math.max(0, Math.max(down(node.left), down(node.right)));
28
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.28 lines

D · Why it works and complexityO(n²) timeO(h) spaceOpen the invariant and proofExplore the proof

The realization that every path has a single bend point converts a scary 'all paths' search into 'for each node, the best path that peaks here'. The only inefficiency is recomputing downward sums — memoizing them into one post-order pass is the whole optimization.

ComplexityO(n²) time, O(h) space — For each of the n possible peak nodes we compute the best downward path into each child, which is an O(n) DFS in the worst case → O(n²) time. Recursion depth is O(h).

E · Edge cases and pitfalls3Recomputing down() for every peak — the source of the quadratic blow-up.Explore edge cases

Pitfalls

Recomputing down() for every peak — the source of the quadratic blow-up.
Returning 0 from the empty subtree but starting best at 0 — breaks all-negative trees.
Forgetting that the peak path uses BOTH arms while down() uses only one.

03.2

Approach 2 of 2 · Optimal

Single Post-Order DFS — Gain Up, Split Recorded (Optimal)

TimeO(n)SpaceO(h)

The answer they want. 'One DFS: each node returns its best single-branch gain; I update a global max with the two-branch split.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

In the brute force, down(x) was recomputed everywhere. What if each node computed its downward gain exactly once and passed it up?

2Hint 2Explore hint

Have the recursion return the best downward gain (one branch). At the same node, while you have both children's gains, compute the bending path (both branches) and update a global best.

3Hint 3Explore hint

Clamp negative child gains to 0 so they're simply skipped. Return val + max(leftGain, rightGain) upward, but record val + leftGain + rightGain as a global candidate.

A · Core idea

Fold the whole computation into one post-order DFS. The key is to keep two related quantities strictly separate.

Quantity 1 — the gain returned upward. When the recursion finishes a node, it returns the maximum sum of a path that starts at this node and goes straight down through at most one child: node.val + max(leftGain, rightGain). We return only one branch because the parent will attach this node as a link in a straight chain — a chain can't pass through both children of a node and still continue upward. We clamp each child's gain at max(gain, 0): if a branch is negative, skipping it (contributing 0) is never worse.

Quantity 2 — the global best (the split). At the same node we also ask: what's the best path whose highest point is this node? Such a path may dip into both children, giving node.val + leftGain + rightGain. This value is not returned upward (a path can't both fork here and extend to the parent), but it's a candidate for the overall answer, so we fold it into a global maximum.

Why these must differ. This is the entire difficulty of the problem. If you returned the split sum (val + left + right) to the parent, the parent could attach a path that already used both of this node's branches and still extend upward — a shape that revisits the node, which paths forbid. Returning only the single best branch keeps every upward extension a legal straight chain, while the global captures the legal bends.

Why post-order. A node can't compute either quantity until it knows both children's gains, so we must finish the children before the parent — that's post-order (left, right, then node).

Why −∞ initialization. The path must be non-empty and values can all be negative, so the answer might be a single negative node. Starting the global at 0 would wrongly return 0 for [-3]. Initialize to −∞ (or to root.val) so the true maximum, however negative, survives.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

The winning bend at node 20

gain(9)

Active call / nodeSupporting contextReturned stateNot active

15 → 20 → 7 = 42 peaks at 20; the negative root is excluded by the max(0, …) clamp.

Final result42

C · Code with teaching comments

solution.javaJava

Single Post-Order DFS — Gain Up, Split Recorded (Optimal) — optimal

4 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
private int best;
9
 
10
public int maxPathSum(TreeNode root) {
11
    // Start at −∞ so an all-negative tree returns its least-negative node, not 0.
12
    best = Integer.MIN_VALUE;
13
    gain(root);
14
    return best;
15
}
16
 
17
// Returns the best single-branch downward gain from node.
18
private int gain(TreeNode node) {
19
    if (node == null) {
20
        return 0;
21
    }
22
    // Clamp negative branches to 0 — skipping them never hurts.
23
    int leftGain = Math.max(gain(node.left), 0);
24
    int rightGain = Math.max(gain(node.right), 0);
25
    best = Math.max(best, node.val + leftGain + rightGain); // split through node
26
    return node.val + Math.max(leftGain, rightGain);        // one branch upward
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

The pattern is 'return a partial result, record a complete result'. The upward return is deliberately weaker (one branch) than the value we score globally (two branches) because the two answer different questions: 'how can my parent use me?' versus 'what's the best path that ends with me at the top?'. This exact split powers Diameter of Binary Tree (return depth, record left+right) and Longest Univalue Path.

ComplexityO(n) time, O(h) space — A single post-order visit touches each node once with O(1) work → O(n) time. The only extra memory is the recursion stack, bounded by the tree height → O(h) space.

E · Edge cases and pitfalls6root = [-3] — Leaf: left=right=0, split = -3 → best = -3; returns -3. The −∞ start is what lets a negative answer win.Explore edge cases

Edge cases handled

root = [-3]Leaf: left=right=0, split = -3 → best = -3; returns -3. The −∞ start is what lets a negative answer win.
All negative, e.g. [-2,-1]Child -1 clamped to 0 for the parent; best becomes max(-1, -2) = -1 — the single least-negative node.
Straight chain [2,-1,3] left-leaningNegative middle is clamped where it would hurt; the algorithm still finds the best contiguous bend or single node.

Pitfalls

Returning val + leftGain + rightGain upward — allows an illegal path that forks and still extends.
Initializing best to 0 — wrong on all-negative trees (returns 0 instead of a negative node).
Forgetting the max(0, gain) clamp — a negative branch then drags the sum down instead of being skipped.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Returning the split sum upward

The value handed to the parent must be a straight downward chain (one child). Returning val + left + right lets the parent extend a path that already used both of this node's branches — a shape that would revisit the node, which paths forbid.

Explore the code comparison

Don't write this

self.best = max(self.best, node.val + left_gain + right_gain)
return node.val + left_gain + right_gain   # illegal: both branches up

Write this instead

self.best = max(self.best, node.val + left_gain + right_gain)
return node.val + max(left_gain, right_gain)  # one branch up

Initializing the answer to zero

The path must contain at least one node and all values can be negative, so the true answer may be negative. Starting at 0 returns 0 for a tree like [-3], which is wrong.

Explore the code comparison

Don't write this

private int best = 0;            // wrong for all-negative trees
// ... best = Math.max(best, node.val + leftGain + rightGain);

Write this instead

private int best = Integer.MIN_VALUE;  // any real path sum can win
// ... best = Math.max(best, node.val + leftGain + rightGain);

Not clamping negative gains

If a child's best downward gain is negative, including it only lowers the sum. Clamping with max(0, gain) lets the algorithm skip that branch entirely.

Explore the code comparison

Don't write this

left_gain = gain(node.left)        # may be negative and dragged in
right_gain = gain(node.right)

Write this instead

left_gain = max(gain(node.left), 0)   # skip harmful branches
right_gain = max(gain(node.right), 0)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Post-order DFS returning a partial value while tracking a global best (split at node)

Code pattern to memorize

self.best = -inf
def gain(node):
    if not node: return 0
    left  = max(gain(node.left), 0)   # drop negative branches
    right = max(gain(node.right), 0)
    self.best = max(self.best, node.val + left + right)  # SPLIT through node
    return node.val + max(left, right)                   # return ONE side up

Rules to remember

1A node returns val + max(left, right) (one branch) — a parent can only extend through a single child.
2A node updates the global with val + left + right (both branches) — the apex of a path that bends here.
3Clamp each child's gain at max(gain, 0) — a negative branch is better skipped than included.
4Initialize the global best to −∞, not 0 — paths must contain at least one node and values can all be negative.
5Use a post-order traversal: children's gains must be known before the parent computes anything.

Use this pattern when

Tree problems asking for an optimum over **paths/subtrees** where the answer can bend at a node
When the value returned to a parent differs from the value you want to record globally
Diameter-style problems: combine two child results at a node, return only one upward
Any 'best path' where including a negative contribution should be optional

Choose another pattern when

Path must go root-to-leaf only → simpler top-down accumulation, no global split needed
You need the actual node sequence, not just the sum → carry/reconstruct the path, more bookkeeping
Graph with cycles, not a tree → DFS recursion no longer guarantees each node once
All values are non-negative AND any path allowed → still works, but the max(…,0) clamps never trigger

Interview takeaway

The defining trick is keeping two quantities apart: the *gain returned upward* uses a single child (so the parent can extend a straight path), while the *global best* allows a split through both children (a path that peaks at this node and can't go higher). This 'return partial, record full' shape is the same engine behind Diameter of Binary Tree and Longest Univalue Path.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternPost-order DFS that returns a partial (single-branch) value while recording a complete (split) value globally. Reach for it whenever the answer can bend at a node but the value you hand a parent must stay a straight chain. Same engine as Diameter of Binary Tree, Longest Univalue Path, and Maximum Sum BST.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Diameter of Binary Tree
Same shape: return depth (one branch) up, record left+right edges as the global diameter.
Longest Univalue Path
Coming soon
Return the longest same-value arm upward; record left+right same-value arms globally.
Maximum Sum BST in Binary Tree
Coming soon
Post-order returning (isBST, min, max, sum); record the max sum among valid BST subtrees.
Find Leaves of Binary Tree
Coming soon
Post-order returning a height index; group nodes by the height returned from below.

Same pattern

←

Construct Binary Tree from Preorder and Inorder Traversal

Continue · Next problem

Average of Levels in Binary Tree

hardTreesLC #124Frequently asked

Binary Tree Maximum Path Sum

LCPractice

Trees & BST · 13 of 41 · 10 min

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**.

In plain English

Examples

Example 1

Input: root = [1,2,3]
Output: 6
Note: The path 2 → 1 → 3 bends at the root and sums to 6.

Example 2

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Note: The best path is 15 → 20 → 7 = 42; it bends at 20 and never touches the negative root.

Example 3

Input: root = [-3]
Output: -3
Note: Single node, all negative — the answer is that one node, which is why we start the global max at −∞.

Constraints

The number of nodes is in the range [1, 3 × 10⁴]
-1000 ≤ Node.val ≤ 1000
The path is non-empty (at least one node) and node values may be negative

Clarifying questions4First question: Does the path have to pass through the root or reach a leaf?Explore questions

Q1.Does the path have to pass through the root or reach a leaf?
No. It can start and end anywhere, as long as the nodes form a connected chain. That's why we track a global maximum across all nodes.
Q2.Can node values be negative?
Yes. So we clamp each child's contribution at 0 (skip negative branches) and initialize the answer to −∞, since even the best single node could be negative.
Q3.Can a path bend (go up through a node and back down)?
Yes, but only once — a path peaks at a single node where it may use both children. Above that node it can only continue through one side.
Q4.Is the path non-empty?
Yes, at least one node. With all-negative values the answer is the single largest (least negative) node.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

How to stand out

Articulate the two quantities precisely, justify the max(0, …) clamp, explain why post-order is required, and note the structural identity with Diameter of Binary Tree.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Best Path Through Each Node	`O(n²)`	`O(h)`	Useful to frame the problem ('every path peaks at some node') before showing how one DFS computes it all in O(n).	Read
2	Single Post-Order DFS — Gain Up, Split Recorded (Optimal)Optimal	`O(n)`	`O(h)`	The answer they want. 'One DFS: each node returns its best single-branch gain; I update a global max with the two-branch split.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Two quantities at each node

How to read it:Return one branch upward (so the parent can extend); record the both-branch split as a candidate global best.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Best Path Through Each Node

TimeO(n²)SpaceO(h)

Useful to frame the problem ('every path peaks at some node') before showing how one DFS computes it all in O(n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Every path has a single highest node where it bends. Can you fix that node and ask: what's the best path peaking here?

2Hint 2Explore hint

For a fixed peak node, the best bending path is its value plus the best downward path into the left subtree plus the best downward path into the right subtree (each clamped at 0).

3Hint 3Explore hint

Computing 'best downward path from X' is itself a recursion. Doing it independently for every candidate peak repeats work — that's the O(n²).

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

peak 9

9 + 0 + 0

Statecandidate = 9

Final result42

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the full code

solution.javaJava

Brute Force — Best Path Through Each Node — reference

3 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
public int maxPathSum(TreeNode root) {
9
    if (root == null) {
10
        return 0;
11
    }
12
    int peakHere = root.val
13
        + Math.max(down(root.left), 0)
14
        + Math.max(down(root.right), 0);
15
    int best = peakHere;
16
    if (root.left != null) best = Math.max(best, maxPathSum(root.left));
17
    if (root.right != null) best = Math.max(best, maxPathSum(root.right));
18
    return best;
19
}
20
 
21
// Best straight downward path starting at node (0 if all negative).
22
private int down(TreeNode node) {
23
    if (node == null) {
24
        return 0;
25
    }
26
    // down(): best straight downward path; recomputed per peak → O(n²).
27
    return node.val + Math.max(0, Math.max(down(node.left), down(node.right)));
28
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.28 lines

D · Why it works and complexityO(n²) timeO(h) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Recomputing down() for every peak — the source of the quadratic blow-up.Explore edge cases

Pitfalls

Recomputing down() for every peak — the source of the quadratic blow-up.
Returning 0 from the empty subtree but starting best at 0 — breaks all-negative trees.
Forgetting that the peak path uses BOTH arms while down() uses only one.

03.2

Approach 2 of 2 · Optimal

Single Post-Order DFS — Gain Up, Split Recorded (Optimal)

TimeO(n)SpaceO(h)

The answer they want. 'One DFS: each node returns its best single-branch gain; I update a global max with the two-branch split.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

In the brute force, down(x) was recomputed everywhere. What if each node computed its downward gain exactly once and passed it up?

2Hint 2Explore hint

Have the recursion return the best downward gain (one branch). At the same node, while you have both children's gains, compute the bending path (both branches) and update a global best.

3Hint 3Explore hint

Clamp negative child gains to 0 so they're simply skipped. Return val + max(leftGain, rightGain) upward, but record val + leftGain + rightGain as a global candidate.

A · Core idea

Fold the whole computation into one post-order DFS. The key is to keep two related quantities strictly separate.

Why post-order. A node can't compute either quantity until it knows both children's gains, so we must finish the children before the parent — that's post-order (left, right, then node).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

The winning bend at node 20

gain(9)

Active call / nodeSupporting contextReturned stateNot active

15 → 20 → 7 = 42 peaks at 20; the negative root is excluded by the max(0, …) clamp.

Final result42

C · Code with teaching comments

solution.javaJava

Single Post-Order DFS — Gain Up, Split Recorded (Optimal) — optimal

4 teaching notes

1
// Definition for a binary tree node.
2
// class TreeNode {
3
//     int val;
4
//     TreeNode left;
5
//     TreeNode right;
6
//     TreeNode(int x) { val = x; }
7
// }
8
private int best;
9
 
10
public int maxPathSum(TreeNode root) {
11
    // Start at −∞ so an all-negative tree returns its least-negative node, not 0.
12
    best = Integer.MIN_VALUE;
13
    gain(root);
14
    return best;
15
}
16
 
17
// Returns the best single-branch downward gain from node.
18
private int gain(TreeNode node) {
19
    if (node == null) {
20
        return 0;
21
    }
22
    // Clamp negative branches to 0 — skipping them never hurts.
23
    int leftGain = Math.max(gain(node.left), 0);
24
    int rightGain = Math.max(gain(node.right), 0);
25
    best = Math.max(best, node.val + leftGain + rightGain); // split through node
26
    return node.val + Math.max(leftGain, rightGain);        // one branch upward
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6root = [-3] — Leaf: left=right=0, split = -3 → best = -3; returns -3. The −∞ start is what lets a negative answer win.Explore edge cases

Edge cases handled

root = [-3]Leaf: left=right=0, split = -3 → best = -3; returns -3. The −∞ start is what lets a negative answer win.
All negative, e.g. [-2,-1]Child -1 clamped to 0 for the parent; best becomes max(-1, -2) = -1 — the single least-negative node.
Straight chain [2,-1,3] left-leaningNegative middle is clamped where it would hurt; the algorithm still finds the best contiguous bend or single node.

Pitfalls

Returning val + leftGain + rightGain upward — allows an illegal path that forks and still extends.
Initializing best to 0 — wrong on all-negative trees (returns 0 instead of a negative node).
Forgetting the max(0, gain) clamp — a negative branch then drags the sum down instead of being skipped.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Returning the split sum upward

Explore the code comparison

Don't write this

self.best = max(self.best, node.val + left_gain + right_gain)
return node.val + left_gain + right_gain   # illegal: both branches up

Write this instead

self.best = max(self.best, node.val + left_gain + right_gain)
return node.val + max(left_gain, right_gain)  # one branch up

Initializing the answer to zero

The path must contain at least one node and all values can be negative, so the true answer may be negative. Starting at 0 returns 0 for a tree like [-3], which is wrong.

Explore the code comparison

Don't write this

private int best = 0;            // wrong for all-negative trees
// ... best = Math.max(best, node.val + leftGain + rightGain);

Write this instead

private int best = Integer.MIN_VALUE;  // any real path sum can win
// ... best = Math.max(best, node.val + leftGain + rightGain);

Not clamping negative gains

If a child's best downward gain is negative, including it only lowers the sum. Clamping with max(0, gain) lets the algorithm skip that branch entirely.

Explore the code comparison

Don't write this

left_gain = gain(node.left)        # may be negative and dragged in
right_gain = gain(node.right)

Write this instead

left_gain = max(gain(node.left), 0)   # skip harmful branches
right_gain = max(gain(node.right), 0)

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Post-order DFS returning a partial value while tracking a global best (split at node)

Code pattern to memorize

self.best = -inf
def gain(node):
    if not node: return 0
    left  = max(gain(node.left), 0)   # drop negative branches
    right = max(gain(node.right), 0)
    self.best = max(self.best, node.val + left + right)  # SPLIT through node
    return node.val + max(left, right)                   # return ONE side up

Rules to remember

1A node returns val + max(left, right) (one branch) — a parent can only extend through a single child.
2A node updates the global with val + left + right (both branches) — the apex of a path that bends here.
3Clamp each child's gain at max(gain, 0) — a negative branch is better skipped than included.
4Initialize the global best to −∞, not 0 — paths must contain at least one node and values can all be negative.
5Use a post-order traversal: children's gains must be known before the parent computes anything.

Use this pattern when

Tree problems asking for an optimum over **paths/subtrees** where the answer can bend at a node
When the value returned to a parent differs from the value you want to record globally
Diameter-style problems: combine two child results at a node, return only one upward
Any 'best path' where including a negative contribution should be optional

Choose another pattern when

Path must go root-to-leaf only → simpler top-down accumulation, no global split needed
You need the actual node sequence, not just the sum → carry/reconstruct the path, more bookkeeping
Graph with cycles, not a tree → DFS recursion no longer guarantees each node once
All values are non-negative AND any path allowed → still works, but the max(…,0) clamps never trigger

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Diameter of Binary Tree
Same shape: return depth (one branch) up, record left+right edges as the global diameter.
Longest Univalue Path
Coming soon
Return the longest same-value arm upward; record left+right same-value arms globally.
Maximum Sum BST in Binary Tree
Coming soon
Post-order returning (isBST, min, max, sum); record the max sum among valid BST subtrees.
Find Leaves of Binary Tree
Coming soon
Post-order returning a height index; group nodes by the height returned from below.

Same pattern

←

Construct Binary Tree from Preorder and Inorder Traversal

Continue · Next problem

Average of Levels in Binary Tree