These are the notes for DSA episode 40. The problem is marked hard, but it is the same pattern as episode 37 (diameter of a binary tree): one postorder pass that returns one value up to the parent and updates a global maximum on the way. Here the value is a sum instead of a height. We start from a real-life road trip, define every word (path, path sum, top of a path, gain, negative values), solve it the obvious way (try every node as the top, O(n · h)), watch it hit Time Limit Exceeded on a big tree, and then solve it in O(n). Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.
The problem, in real life
You are planning a road trip. The towns are joined by roads, and the map has a special shape: between any two towns there is exactly one route, no loops. That shape is a tree. You are a musician: some towns hold a fair and pay you (+15, +20); some towns charge a toll to pass through (−10). You may start in any town and end in any town, but you can never visit a town twice. Which trip earns the most money?
| On the road trip | In a binary tree |
|---|---|
| A town | a node |
| The money a town pays (or charges) | the node's value (can be negative) |
| A road between two towns | an edge |
| Your trip, no town twice | a path |
| The money you end with | the path sum |
| The highest town on your trip (closest to the capital) | the top of the path |
| The best money from a town going only "away from the capital" | the gain of a node |
| Not taking a toll road at all | clamping a negative gain to 0 |
The freedom to start and end anywhere is what makes the problem hard: the best trip need not touch the root, and need not reach a leaf.
Every word, from zero
- Binary tree, node, edge, root, parent, child, leaf: from episode 36. A node has a value
valand up to two children,leftandright;nullmeans "no child". - Path: a sequence of nodes where each node is joined to the next by an edge, and no node appears twice. A path has at least one node. It may start and end anywhere; it need not include the root or a leaf.
- Path sum: the total of the values of the nodes on the path.
- Negative values: a node can be worth less than zero (a toll). Then the best path may stop before it.
- Top of a path: the node of the path that is closest to the root. Every path has exactly one top. The path goes up from one side to the top, then down the other side (like a mountain road over a pass). Either side may be empty.
- Fork: a set of nodes where one node would need three edges in the path (two children and its parent). A fork is not a path.
- Gain of a node: the best sum of a path that starts at that node and goes straight down, choosing one child at each step (or stopping). For a leaf, gain = its value.
- Clamping: replacing a negative number by 0, with
Math.max(0, x). A negative gain means "don't go down there", which is worth 0. - Postorder: visit left subtree, right subtree, then the node (episode 36). It lets each node use its children's answers.
- Global maximum: a variable outside the recursion (
static int best) that every call can update.
Our familiar tree from episode 36:
1
/ \
2 3
/ \ \
4 5 6
| Nodes | Path? | Top | Sum |
|---|---|---|---|
| 4 → 2 → 5 | yes | 2 | 11 |
| 5 → 2 → 1 → 3 → 6 | yes (the best here) | 1 | 17 |
| 6 | yes (one node) | 6 | 6 |
| 4, 5, 2, 1 | no: 2 would use three edges (a fork) |
Problem statement
Binary Tree Maximum Path Sum (LeetCode 124). Given the root of a non-empty binary tree, return the maximum path sum of any path. Values are between −1000 and 1000; LeetCode's trees have up to 3 · 10^4 nodes.
[1, 2, 3] → 6 (2 → 1 → 3)
[-10, 9, 20, null, null, 15, 7] → 42 (15 → 20 → 7, skips the root)
[-3] → -3 (one node: the path cannot be empty)
The array form is level order with null for missing children: [-10, 9, 20, null, null, 15, 7] is
-10
/ \
9 20
/ \
15 7
In Java we build the examples directly:
Node a = new Node(1, new Node(2), new Node(3));
Node b = new Node(-10, new Node(9),
new Node(20, new Node(15), new Node(7)));
Node c = new Node(-3);
Brute force: try every node as the top
Every path has exactly one top. So for every node n, compute the best straight-down sum on its left and on its right with a fresh recursion down(), clamp each at 0, and form n.val + L + R. The answer is the largest of these.
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static int down(Node n) {
if (n == null) return 0;
int best = Math.max(down(n.left), down(n.right));
return n.val + Math.max(0, best);
}
static int bruteMax(Node n) {
if (n == null) return Integer.MIN_VALUE;
int L = Math.max(0, down(n.left));
int R = Math.max(0, down(n.right));
int top = n.val + L + R;
return Math.max(top, Math.max(bruteMax(n.left), bruteMax(n.right)));
}
public static void main(String[] args) {
Node a = new Node(1, new Node(2), new Node(3));
Node b = new Node(-10, new Node(9),
new Node(20, new Node(15), new Node(7)));
Node c = new Node(-3);
System.out.println(bruteMax(a));
System.out.println(bruteMax(b));
System.out.println(bruteMax(c));
}
}
Real output:
6
42
-3
Correct on all three examples. Integer.MIN_VALUE (−2,147,483,648, the smallest int) is returned for an empty subtree so it never wins the Math.max.
A big tree: Time Limit Exceeded
A chain of 6,000 nodes (each the left child of the previous one), with a complete tree 20 levels deep (2^20 − 1 ≈ 10 lakh nodes) hung at the bottom. Values are random in −100 .. 100 (new Random(40), so every run builds the same tree).
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static int down(Node n) {
if (n == null) return 0;
int best = Math.max(down(n.left), down(n.right));
return n.val + Math.max(0, best);
}
static int bruteMax(Node n) {
if (n == null) return Integer.MIN_VALUE;
int L = Math.max(0, down(n.left));
int R = Math.max(0, down(n.right));
int top = n.val + L + R;
return Math.max(top, Math.max(bruteMax(n.left), bruteMax(n.right)));
}
static Random rnd = new Random(40);
static int r() { return rnd.nextInt(201) - 100; }
static Node full(int d) {
if (d == 0) return null;
return new Node(r(), full(d - 1), full(d - 1));
}
static Node bigTree() {
Node root = new Node(r()), cur = root;
for (int i = 1; i < 6000; i++) {
cur.left = new Node(r());
cur = cur.left;
}
cur.left = full(20);
return root;
}
public static void main(String[] args) {
Node big = bigTree();
long t0 = System.nanoTime();
int ans = bruteMax(big);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("best = " + ans + ", " + ms + " ms");
}
}
Real result in the compiler: Time Limit Exceeded (killed at 8 s). Run locally without a limit it printed best = 3505, 34401 ms (and 36892 ms on a second run): more than 30 seconds.
Why the brute force is slow
down(n) walks every node below n. bruteMax calls it for every node, so a node is walked once by each of its ancestors. The ten lakh bottom nodes have more than 6,000 ancestors each: about 6,000 × 10,00,000 ≈ 600 crore (6 billion) node visits. In general the cost is the sum of all subtree sizes, which is O(n · h) for n nodes and height h; on a plain chain h = n, so it is O(n²).
The waste: node 20 computes its gain from 15 and 7; then its parent asks 20 again, which asks 15 and 7 again. Each node should compute its gain once and hand it up.
The key insight: one postorder pass
This is the diameter pattern from episode 37 (there: return the height up, update the best diameter). Here, for every node n, after both children have answered:
L = max(0, gain(left)),R = max(0, gain(right)): a negative branch is a toll road, so it is worth 0 (don't take it).- As the top, the path can use both sides:
best = max(best, n.val + L + R). - To the parent, return one side only:
n.val + max(L, R). If the path continues up to the parent, it cannot also fork into both children.
Both sides to update the answer, one side to return.
Trace on example 2:
| Node (postorder) | L | R | as the top: val + L + R | best | returns val + max(L, R) |
|---|---|---|---|---|---|
| 9 | 0 | 0 | 9 | 9 | 9 |
| 15 | 0 | 0 | 15 | 15 | 15 |
| 7 | 0 | 0 | 7 | 15 | 7 |
| 20 | 15 | 7 | 42 | 42 | 35 |
| −10 | 9 | 35 | 34 | 42 | 25 |
Answer 42: the path 15 → 20 → 7, which never touches the root. The global best caught it at node 20.
The optimal solution in Java
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static int best;
static int gain(Node n) {
if (n == null) return 0;
int L = Math.max(0, gain(n.left));
int R = Math.max(0, gain(n.right));
best = Math.max(best, n.val + L + R);
return n.val + Math.max(L, R);
}
static int maxPathSum(Node root) {
best = Integer.MIN_VALUE;
gain(root);
return best;
}
public static void main(String[] args) {
Node a = new Node(1, new Node(2), new Node(3));
Node b = new Node(-10, new Node(9),
new Node(20, new Node(15), new Node(7)));
Node c = new Node(-3);
Node d = new Node(-2, new Node(-1), new Node(-3));
Node e = new Node(10, new Node(-20, new Node(15), null), null);
System.out.println(maxPathSum(a));
System.out.println(maxPathSum(b));
System.out.println(maxPathSum(c));
System.out.println(maxPathSum(d));
System.out.println(maxPathSum(e));
}
}
Real output:
6
42
-3
-1
15
a,b,c: the three LeetCode examples.d(−2 with children −1 and −3, all negative): −1, just the least bad node.e(a chain 10 → −20 → 15): 15. The whole chain is only 10 − 20 + 15 = 5, so the best trip is the town 15 alone.
The big tree in milliseconds
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static int best;
static int gain(Node n) {
if (n == null) return 0;
int L = Math.max(0, gain(n.left));
int R = Math.max(0, gain(n.right));
best = Math.max(best, n.val + L + R);
return n.val + Math.max(L, R);
}
static int maxPathSum(Node root) {
best = Integer.MIN_VALUE;
gain(root);
return best;
}
static Random rnd = new Random(40);
static int r() { return rnd.nextInt(201) - 100; }
static Node full(int d) {
if (d == 0) return null;
return new Node(r(), full(d - 1), full(d - 1));
}
static Node bigTree() {
Node root = new Node(r()), cur = root;
for (int i = 1; i < 6000; i++) {
cur.left = new Node(r());
cur = cur.left;
}
cur.left = full(20);
return root;
}
public static void main(String[] args) {
Node big = bigTree();
long t0 = System.nanoTime();
int ans = maxPathSum(big);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("best = " + ans + ", " + ms + " ms");
}
}
Real output: best = 3505, 13 ms (12 to 16 ms over several runs). The same answer as the brute force, which needed more than 30 seconds.
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
Node *left, *right;
Node(int v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};
int best;
int gain(Node* n) {
if (!n) return 0;
int L = max(0, gain(n->left));
int R = max(0, gain(n->right));
best = max(best, n->val + L + R);
return n->val + max(L, R);
}
int maxPathSum(Node* root) {
best = INT_MIN;
gain(root);
return best;
}
int main() {
Node* a = new Node(1, new Node(2), new Node(3));
Node* b = new Node(-10, new Node(9), new Node(20, new Node(15), new Node(7)));
Node* c = new Node(-3);
Node* d = new Node(-2, new Node(-1), new Node(-3));
Node* e = new Node(10, new Node(-20, new Node(15)));
for (Node* t : {a, b, c, d, e}) cout << maxPathSum(t) << '\n';
}
Compiled with g++ -O2 -std=c++17. Real output:
6
42
-3
-1
15
INT_MIN plays the role of Integer.MIN_VALUE.
The same solution in Python
import sys
sys.setrecursionlimit(100000)
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def max_path_sum(root):
best = float("-inf")
def gain(n):
nonlocal best
if n is None:
return 0
L = max(0, gain(n.left))
R = max(0, gain(n.right))
best = max(best, n.val + L + R)
return n.val + max(L, R)
gain(root)
return best
a = Node(1, Node(2), Node(3))
b = Node(-10, Node(9), Node(20, Node(15), Node(7)))
c = Node(-3)
d = Node(-2, Node(-1), Node(-3))
e = Node(10, Node(-20, Node(15)))
for t in (a, b, c, d, e):
print(max_path_sum(t))
Real output:
6
42
-3
-1
15
nonlocal best lets the inner function update the variable of max_path_sum. Python's default recursion limit is 1000; on a 5,000-node chain without sys.setrecursionlimit it fails with RecursionError: maximum recursion depth exceeded.
Three real bugs
Bug 1: returning both sides to the parent
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static int best;
static int gain(Node n) {
if (n == null) return 0;
int L = Math.max(0, gain(n.left));
int R = Math.max(0, gain(n.right));
best = Math.max(best, n.val + L + R);
return n.val + L + R;
}
static int maxPathSum(Node root) {
best = Integer.MIN_VALUE;
gain(root);
return best;
}
public static void main(String[] args) {
Node t = new Node(1, new Node(2, new Node(4), new Node(5)),
new Node(3, null, new Node(6)));
System.out.println(maxPathSum(t));
}
}
Real output: 21. The right answer for this tree is 17 (5 → 2 → 1 → 3 → 6). Node 2 returned 2 + 4 + 5 = 11 (a fork), node 3 returned 9, and the root formed 1 + 11 + 9 = 21, which is the set {4, 5, 2, 1, 3, 6}: not a path. Fix: return n.val + Math.max(L, R);.
Bug 2: starting best at 0
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static int best;
static int gain(Node n) {
if (n == null) return 0;
int L = Math.max(0, gain(n.left));
int R = Math.max(0, gain(n.right));
best = Math.max(best, n.val + L + R);
return n.val + Math.max(L, R);
}
static int maxPathSum(Node root) {
best = 0;
gain(root);
return best;
}
public static void main(String[] args) {
System.out.println(maxPathSum(new Node(-3)));
System.out.println(maxPathSum(new Node(-2, new Node(-1), new Node(-3))));
}
}
Real output:
0
0
The answers are −3 and −1. Zero is the sum of the empty path, which is not allowed, and no real path ever beats it in an all-negative tree. Fix: best = Integer.MIN_VALUE;.
Bug 3: not clamping negative gains
import java.util.*;
public class Main {
static class Node {
int val;
Node left, right;
Node(int v) { val = v; }
Node(int v, Node l, Node r) { val = v; left = l; right = r; }
}
static int best;
static int gain(Node n) {
if (n == null) return 0;
int L = gain(n.left);
int R = gain(n.right);
best = Math.max(best, n.val + L + R);
return n.val + Math.max(L, R);
}
static int maxPathSum(Node root) {
best = Integer.MIN_VALUE;
gain(root);
return best;
}
public static void main(String[] args) {
System.out.println(maxPathSum(new Node(5, new Node(-8), new Node(4))));
}
}
Real output: 4. The right answer is 5 + 4 = 9. Without Math.max(0, ...), node 5 was forced to take the −8 branch: −8 + 5 + 4 = 1, so the best found was the single node 4. Fix: int L = Math.max(0, gain(n.left)); (and the same for R).
Also: very deep trees
Recursion uses one stack frame per level. With Java's default stack, the optimal gain on a chain worked at 20,000 levels and failed at 22,000 (and at 50,000) with:
Exception in thread "main" java.lang.StackOverflowError
at Main.gain(Main.java:6)
Our big tree is about 6,000 levels deep, so it is safe. For deeper trees use an iterative postorder (practice question 4) or run the work in a Thread with a bigger stack size.
Complexity
| Approach | Time | Extra space | Big tree (6,000-chain + 10 lakh nodes) |
|---|---|---|---|
Every node as the top, fresh down() calls |
O(n · h), O(n²) on a chain | O(h) recursion | more than 30 s: TLE |
One postorder pass (gain + global best) |
O(n) | O(h) recursion | about 15 ms |
h is about log₂ n for a balanced tree and n for a chain.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
return n.val + L + R; |
21 instead of 17 |
a fork is sent up to the parent | return n.val + Math.max(L, R); |
best = 0; |
0 instead of -3 (and -1) |
the empty path is not allowed | best = Integer.MIN_VALUE; |
int L = gain(n.left); (no clamp) |
4 instead of 9 |
negative branches are forced into the path | Math.max(0, gain(n.left)) |
| Only considering paths through the root | 34 instead of 42 on example 2 |
the best path may skip the root | update best at every node |
| Recursion on a 22,000+ level chain | java.lang.StackOverflowError |
one stack frame per level | iterative postorder, or a bigger thread stack |
| Python without a raised limit | RecursionError: maximum recursion depth exceeded |
default limit 1000 | sys.setrecursionlimit(...) or iterative |
Forgetting to reset best between calls |
a later tree can report an earlier tree's answer | best is static |
set it in maxPathSum before calling gain |
Mini project: the road-trip planner
Make a Town node with a String name and an int money. Build a small map as a binary tree (say 8 towns, some paying, some charging tolls). Print the best trip as a route of names and its total, for example Fairpur → Melaganj → Tollnagar → ... = 42. Hint: practice question 1 returns the path itself. Then print, for every town, its gain (the best trip that starts there and heads away from the capital).
Practice
- Return the best path itself, not only its sum.
Solution
Make the recursion return the best straight-down path as a list (top first). At each node, if n.val + L + R beats best, build the path: the left list reversed (if L > 0), then n.val, then the right list (if R > 0). Return n.val followed by the better child's list (if it is positive).
static int best;
static List<Integer> bestPath;
static List<Integer> down(Node n) { // best straight-down path, top first
if (n == null) return new ArrayList<>();
List<Integer> l = down(n.left), r = down(n.right);
int L = Math.max(0, sum(l)), R = Math.max(0, sum(r));
if (n.val + L + R > best) {
best = n.val + L + R;
List<Integer> p = new ArrayList<>();
if (L > 0) { p.addAll(l); Collections.reverse(p); }
p.add(n.val);
if (R > 0) p.addAll(r);
bestPath = p;
}
List<Integer> up = new ArrayList<>();
up.add(n.val);
if (Math.max(L, R) > 0) up.addAll(L >= R ? l : r);
return up;
}
static int sum(List<Integer> p) { int s = 0; for (int x : p) s += x; return s; }
Real output (with best = Integer.MIN_VALUE before each call): example 2 → 42 [15, 20, 7], the episode-36 tree → 17 [5, 2, 1, 3, 6]. (Summing the lists makes it O(n · h); to stay O(n), return the gain alongside the list.)
- Maximum root-to-leaf path sum (the path must start at the root and end at a leaf).
Solution
Only one branch, no global needed, and no clamping (you must reach a leaf):
static int rootToLeaf(Node n) {
if (n.left == null && n.right == null) return n.val;
int b = Integer.MIN_VALUE;
if (n.left != null) b = Math.max(b, rootToLeaf(n.left));
if (n.right != null) b = Math.max(b, rootToLeaf(n.right));
return n.val + b;
}
Real output: example 2 → 25 (−10 → 20 → 15), the episode-36 tree → 10 (1 → 3 → 6).
- Longest univalue path (LeetCode 687): the longest path (in edges) where all nodes have the same value.
Solution
The same "both sides for the answer, one side to return" pattern. A child's arm counts only if its value equals the node's value.
static int longest;
static int uni(Node n) {
if (n == null) return 0;
int l = uni(n.left), r = uni(n.right);
int L = (n.left != null && n.left.val == n.val) ? l + 1 : 0;
int R = (n.right != null && n.right.val == n.val) ? r + 1 : 0;
longest = Math.max(longest, L + R);
return Math.max(L, R);
}
For the tree 5 → (4 → 1, 1), (5 → right 5) the real output is 2 (5 → 5 → 5).
- Maximum path sum without recursion (safe on any depth).
Solution
Collect the nodes with a stack in "node, then children" order; reading that list backwards visits every child before its parent. Store each node's gain in a map.
static int iterMax(Node root) {
Map<Node, Integer> g = new HashMap<>();
Deque<Node> st = new ArrayDeque<>();
List<Node> order = new ArrayList<>();
st.push(root);
while (!st.isEmpty()) {
Node n = st.pop();
order.add(n);
if (n.left != null) st.push(n.left);
if (n.right != null) st.push(n.right);
}
int ans = Integer.MIN_VALUE;
for (int i = order.size() - 1; i >= 0; i--) { // children before parents
Node n = order.get(i);
int L = Math.max(0, g.getOrDefault(n.left, 0));
int R = Math.max(0, g.getOrDefault(n.right, 0));
ans = Math.max(ans, n.val + L + R);
g.put(n, n.val + Math.max(L, R));
}
return ans;
}
Real output: example 2 → 42, the episode-36 tree → 17, and a chain of 1,00,000 nodes of value 1 → 100000 (no StackOverflowError). g.getOrDefault(null, 0) returns 0 for a missing child, since HashMap allows a null key lookup.
Quick quiz
In example 2 (-10 → 9, (20 → 15, 7)), what does gain(20) return to its parent: 42, 35, 27 or 20?
Answer
35 = 20 + max(15, 7). The parent can continue down only one branch. 42 uses both branches, so it only updates best; it never goes up.
Interview questions
- Why does
gainreturn one branch butbestuse two? A path that continues to the parent can enter this node from only one child; a path whose top is this node can use both children. - Why clamp at 0? A negative gain lowers any sum it is added to, so "don't go down that side" (worth 0) is always at least as good.
- Why initialise
besttoInteger.MIN_VALUE, not 0? The path must contain at least one node; in an all-negative tree every path is negative. - Time and space? O(n) time (each node once, constant work), O(h) space for the recursion.
- How is this related to the diameter problem? Same structure: postorder, return one arm (height / gain) up, update a global with both arms (left + right edges / L + val + R).
- What if the tree has 10^5 levels? Recursion can overflow the stack (
StackOverflowErrorin Java,RecursionErrorin Python); use an iterative postorder. - Can the answer overflow
int? Not under LeetCode's limits (3 · 10^4 nodes × 1000 = 3 · 10^7). With bigger values or counts, uselong.
Glossary
| Term | Meaning |
|---|---|
| Binary tree | A tree where every node has at most two children, left and right |
| Node / value | One item of the tree; here it holds an int val that may be negative |
| Edge | The link between a parent and a child |
| Path | Nodes joined by edges one after another, no node twice, at least one node |
| Path sum | The sum of the values of the nodes on a path |
| Top of a path | The node of the path closest to the root; the path goes up to it, then down |
| Fork | Three edges meeting at one node of the chosen set; not a path |
| Gain | The best sum of a path that starts at a node and goes straight down (one child per step) |
| Clamping | Replacing a negative value by 0: Math.max(0, x) |
| Postorder | Left subtree, right subtree, then the node; children answer first |
| Global maximum | A variable outside the recursion (static int best) updated by every call |
Integer.MIN_VALUE |
The smallest Java int, −2,147,483,648; a safe starting value for a maximum |
| Brute force | The obvious, slow method: here, every node as the top with fresh recursive calls |
| O(n · h), O(n²) | Running time growing with nodes × height; squared on a chain |
| Time Limit Exceeded (TLE) | The program was stopped for running too long (8 s in the SyntaxPilot compiler) |
StackOverflowError |
Java's error when recursion goes too deep for the call stack |
RecursionError |
Python's error when recursion passes the recursion limit (default 1000) |
Summary
- A path is connected nodes, no node twice, at least one node; it may skip the root. Every path has one top.
- Gain of a node = best straight-down sum from it:
val + max(0, gain(left), gain(right)). - Brute force (every node as the top, fresh calls) is O(n · h): TLE on a tall tree.
- One postorder pass: clamp children's gains at 0,
best = max(best, val + L + R)(both sides), returnval + max(L, R)(one side). StartbestatInteger.MIN_VALUE. O(n) time, O(h) space.
Next episode: Serialize and deserialize a binary tree (hard).