DSA-088 · One parent-extendable gain versus a global two-arm path
Binary Tree Maximum Path Sum
Advanced · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 23506 deterministic checks. Learner drafts are not executed.
Understand the problem
Return the greatest sum of values on a nonempty simple path in a binary tree. A path may start and end anywhere and may cross one node between two child arms.
- Input roots are null or finite proper binary trees with at most 100,000 nodes per tree: no cycles and no shared child within one tree. Values span the full int domain. Structure/size are preconditions, not an extra validation traversal.
- Preserve every original value, node identity, and left/right edge. Compact level-order arrays in examples are adapters, consuming two child slots per nonnull queued parent; they are not heap-indexed arrays.
- Return OptionalLong.empty for null input because no nonempty path exists. Otherwise return a present long, including negative optima. A path cannot repeat a node or branch into three arms. With at most 100,000 int values, every path sum fits long; widen before addition.
Examples
Input:
[-10,9,20,null,null,15,7]
Output:OptionalLong[42]The path 15–20–7 beats every path through root -10.
Input:
[-3,-2,-5]
Output:OptionalLong[-2]A nonempty optimum may be a single negative node; zero is not allowed as the answer.
Input:
[MAX,MAX,MAX]
Output:OptionalLong[6442450941]The three-node sum exceeds int capacity.
Before you start
- Diameter’s postorder decomposition
- Long arithmetic, negative contributions and nonempty optima
Recognize the structure
Like diameter, every path has a unique highest node. A child can supply one downward path gain to its parent. Negative gains are omitted locally, but the current node remains mandatory in every global candidate.
Try before revealing
Hint 1
What may a child return that can still be extended by its parent?
Hint 2
Negative child arms are optional, but the current node is not.
Hint 3
In postorder, update best with value+both nonnegative arms and return value+the better one.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Recursive gain combination
Recursively compute each child’s best downward gain, clamp optional child gains to zero, update global best with value+left+right, and return value+max(left,right). For [-3,-2,-5], candidate -2 is retained even though its parent should discard that negative child gain. Work is already O(n); explicit frames make the same recurrence safe on deep trees.
Improve the baseline
Store raw child gains in continuation frames
Frame fields hold the actual best nonempty downward gain for each child, possibly negative. Missing children contribute zero. Postorder stages ensure these values exist before combining.
Evaluate a nonempty two-arm candidate
Set left=max(0,leftGain), right=max(0,rightGain). Compare global best with (long)value+left+right; initialize best to Long.MIN_VALUE rather than zero.
Return only one arm upward
The parent receives value+max(left,right). Passing both arms would create a branching structure if a parent extends it, which is not a simple path.
Why it is correct
Downward-gain induction
For a fixed node, a parent-extendable path must start there and choose at most one child arm. Omitting a negative arm is optimal; the recurrence returns the greatest such nonempty downward sum.
Global path completeness
Any nonempty simple path has one highest node and at most one arm in each child subtree. At that node the candidate chooses the best nonnegative optional arm on each side, dominating that path.
Nonempty and numeric correctness
Every candidate includes the current node, so all-negative trees choose the least-negative available path rather than an empty zero. All sums widen to long and remain within the declared bound.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.*;
public final class Solution {
public static final class Node {
public final int value;
public Node left, right;
public Node(int value) { this.value = value; }
}
private static final class Frame {
final Node node;
int stage;
long leftGain, rightGain;
Frame(Node node) { this.node = node; }
}
public static OptionalLong maximumPathSum(Node root) {
if (root == null) return OptionalLong.empty();
ArrayDeque<Frame> stack = new ArrayDeque<>(); stack.push(new Frame(root));
long best = Long.MIN_VALUE;
while (!stack.isEmpty()) {
Frame frame = stack.peek();
if (frame.stage == 0) {
frame.stage = 1;
if (frame.node.left != null) stack.push(new Frame(frame.node.left));
} else if (frame.stage == 1) {
frame.stage = 2;
if (frame.node.right != null) stack.push(new Frame(frame.node.right));
} else {
long left = Math.max(0L,frame.leftGain), right = Math.max(0L,frame.rightGain);
best = Math.max(best,(long) frame.node.value+left+right);
long gain = (long) frame.node.value+Math.max(left,right);
stack.pop();
if (!stack.isEmpty()) {
Frame parent = stack.peek();
if (parent.stage == 1) parent.leftGain = gain;
else parent.rightGain = gain;
}
}
}
return OptionalLong.of(best);
}
private static long gain(Node node, long[] best) {
if (node == null) return 0;
long left = Math.max(0L,gain(node.left,best)), right = Math.max(0L,gain(node.right,best));
best[0] = Math.max(best[0],(long) node.value+left+right);
return (long) node.value+Math.max(left,right);
}
public static OptionalLong baseline(Node root) {
if (root == null) return OptionalLong.empty();
long[] best = {Long.MIN_VALUE}; gain(root,best); return OptionalLong.of(best[0]);
}
}
Read the meaningful blocks
Raw returned gains may be negative
Clamping happens when a parent chooses an optional child arm; the child’s own nonempty candidate must still be considered.
Keep best local to the call
A local long best prevents cross-call state leakage and supports repeat queries.
OptionalLong describes empty input honestly
Long.MIN_VALUE is an internal initialization only, not a public no-answer sentinel; all int-valued single-node paths remain valid.
Complexity
O(n) time and O(h) live explicit frames. Each frame combines once, and no O(n) gain map is retained. The output is one OptionalLong; the source tree is read-only.
Recursive baseline work is also O(n) with O(h) call frames but is limited to shallow inputs. The independent test oracle enumerates all endpoint paths in O(n²) on bounded trees; it is not the production algorithm.
Exact-state walkthroughs
Reveal normal and boundary traces
The winning path can avoid the root
Input: [-10,9,20,null,null,15,7] · Optional nonempty path sum: {"present":true,"value":42}
Step 1 of 17: Create explicit postorder continuations.
Stack top is at the right. Child result fields start at zero. A stage-2 frame combines only when it is top again, after both existing children return.
Phase: initial. Current identity: null.
Original objects — unchanged source edges
- T0: -10left → T1right → T2
- T1: 9left → nullright → null
- T2: 20left → T3right → T4
- T3: 15left → nullright → null
- T4: 7left → nullright → null
Postorder continuations — stack top at right
- T0: stage 0; left 0; right 0
Stage 0 enters left; stage 1 continues into right; stage 2 combines when that frame becomes top again. Child summaries are stored in the parent frame.
Best completed candidate: none yet. Only one arm returns upward; the global candidate may use both nonnegative arms and must include the current node.
Completed-node summaries in the table are teaching history; Java retains only live frames and the scalar best.
Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.
| Variable | Value |
|---|---|
| treeNodes | [{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}] |
| root | "T0" |
| stack | [{"id":"T0","stage":0,"leftGain":0,"rightGain":0}] |
| summaries | [] |
| best | null |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 public static final class Node { 4 public final int value; 5 public Node left, right; 6 public Node(int value) { this.value = value; } 7 } 8 private static final class Frame { 9 final Node node; 10 int stage; 11 long leftGain, rightGain; 12 Frame(Node node) { this.node = node; } 13 } 14 public static OptionalLong maximumPathSum(Node root) { 15 if (root == null) return OptionalLong.empty(); 16 ArrayDeque<Frame> stack = new ArrayDeque<>(); stack.push(new Frame(root)); 17 long best = Long.MIN_VALUE; 18 while (!stack.isEmpty()) { 19 Frame frame = stack.peek(); 20 if (frame.stage == 0) { 21 frame.stage = 1; 22 if (frame.node.left != null) stack.push(new Frame(frame.node.left)); 23 } else if (frame.stage == 1) { 24 frame.stage = 2; 25 if (frame.node.right != null) stack.push(new Frame(frame.node.right)); 26 } else { 27 long left = Math.max(0L,frame.leftGain), right = Math.max(0L,frame.rightGain); 28 best = Math.max(best,(long) frame.node.value+left+right); 29 long gain = (long) frame.node.value+Math.max(left,right); 30 stack.pop(); 31 if (!stack.isEmpty()) { 32 Frame parent = stack.peek(); 33 if (parent.stage == 1) parent.leftGain = gain; 34 else parent.rightGain = gain; 35 } 36 } 37 } 38 return OptionalLong.of(best); 39 } 40 private static long gain(Node node, long[] best) { 41 if (node == null) return 0; 42 long left = Math.max(0L,gain(node.left,best)), right = Math.max(0L,gain(node.right,best)); 43 best[0] = Math.max(best[0],(long) node.value+left+right); 44 return (long) node.value+Math.max(left,right); 45 } 46 public static OptionalLong baseline(Node root) { 47 if (root == null) return OptionalLong.empty(); 48 long[] best = {Long.MIN_VALUE}; gain(root,best); return OptionalLong.of(best[0]); 49 } 50 } 51
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Create explicit postorder continuations.
Stack top is at the right. Child result fields start at zero. A stage-2 frame combines only when it is top again, after both existing children return.
- treeNodes
[{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":0,"leftGain":0,"rightGain":0}]- summaries
[]- best
null- phase
"initial"- current
null
- Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":1,"leftGain":0,"rightGain":0},{"id":"T1","stage":0,"leftGain":0,"rightGain":0}]- summaries
[]- best
null- phase
"enter-left"- current
"T0"
- Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":1,"leftGain":0,"rightGain":0},{"id":"T1","stage":1,"leftGain":0,"rightGain":0}]- summaries
[]- best
null- phase
"enter-left"- current
"T1"
- Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":1,"leftGain":0,"rightGain":0},{"id":"T1","stage":2,"leftGain":0,"rightGain":0}]- summaries
[]- best
null- phase
"enter-right"- current
"T1"
- Combine child results and return one parent-extendable summary.
The global candidate can use two arms, but only one arm is returned upward. A negative node is still a nonempty candidate.
- treeNodes
[{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":1,"leftGain":9,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":9,"gain":9}]- best
9- phase
"combine"- current
"T1"- last
{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":9,"gain":9}
- Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":9,"rightGain":0},{"id":"T2","stage":0,"leftGain":0,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":9,"gain":9}]- best
9- phase
"enter-right"- current
"T0"
- Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":9,"rightGain":0},{"id":"T2","stage":1,"leftGain":0,"rightGain":0},{"id":"T3","stage":0,"leftGain":0,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":9,"gain":9}]- best
9- phase
"enter-left"- current
"T2"
- Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":9,"rightGain":0},{"id":"T2","stage":1,"leftGain":0,"rightGain":0},{"id":"T3","stage":1,"leftGain":0,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":9,"gain":9}]- best
9- phase
"enter-left"- current
"T3"
- Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":9,"rightGain":0},{"id":"T2","stage":1,"leftGain":0,"rightGain":0},{"id":"T3","stage":2,"leftGain":0,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":9,"gain":9}]- best
9- phase
"enter-right"- current
"T3"
- Combine child results and return one parent-extendable summary.
The global candidate can use two arms, but only one arm is returned upward. A negative node is still a nonempty candidate.
- treeNodes
[{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":9,"rightGain":0},{"id":"T2","stage":1,"leftGain":15,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":9,"gain":9},{"id":"T3","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":15,"gain":15}]- best
15- phase
"combine"- current
"T3"- last
{"id":"T3","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":15,"gain":15}
- Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":9,"rightGain":0},{"id":"T2","stage":2,"leftGain":15,"rightGain":0},{"id":"T4","stage":0,"leftGain":0,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":9,"gain":9},{"id":"T3","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":15,"gain":15}]- best
15- phase
"enter-right"- current
"T2"
- Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":9,"rightGain":0},{"id":"T2","stage":2,"leftGain":15,"rightGain":0},{"id":"T4","stage":1,"leftGain":0,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":9,"gain":9},{"id":"T3","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":15,"gain":15}]- best
15- phase
"enter-left"- current
"T4"
- Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":9,"rightGain":0},{"id":"T2","stage":2,"leftGain":15,"rightGain":0},{"id":"T4","stage":2,"leftGain":0,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":9,"gain":9},{"id":"T3","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":15,"gain":15}]- best
15- phase
"enter-right"- current
"T4"
- Combine child results and return one parent-extendable summary.
The global candidate can use two arms, but only one arm is returned upward. A negative node is still a nonempty candidate.
- treeNodes
[{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":9,"rightGain":0},{"id":"T2","stage":2,"leftGain":15,"rightGain":7}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":9,"gain":9},{"id":"T3","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":15,"gain":15},{"id":"T4","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":7,"gain":7}]- best
15- phase
"combine"- current
"T4"- last
{"id":"T4","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":7,"gain":7}
- Combine child results and return one parent-extendable summary.
The global candidate can use two arms, but only one arm is returned upward. A negative node is still a nonempty candidate.
- treeNodes
[{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":9,"rightGain":35}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":9,"gain":9},{"id":"T3","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":15,"gain":15},{"id":"T4","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":7,"gain":7},{"id":"T2","leftGain":15,"rightGain":7,"leftArm":15,"rightArm":7,"candidate":42,"gain":35}]- best
42- phase
"combine"- current
"T2"- last
{"id":"T2","leftGain":15,"rightGain":7,"leftArm":15,"rightArm":7,"candidate":42,"gain":35}
- Combine child results and return one parent-extendable summary.
The global candidate can use two arms, but only one arm is returned upward. A negative node is still a nonempty candidate.
- treeNodes
[{"id":"T0","value":-10,"left":"T1","right":"T2"},{"id":"T1","value":9,"left":null,"right":null},{"id":"T2","value":20,"left":"T3","right":"T4"},{"id":"T3","value":15,"left":null,"right":null},{"id":"T4","value":7,"left":null,"right":null}]- root
"T0"- stack
[]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":9,"gain":9},{"id":"T3","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":15,"gain":15},{"id":"T4","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":7,"gain":7},{"id":"T2","leftGain":15,"rightGain":7,"leftArm":15,"rightArm":7,"candidate":42,"gain":35},{"id":"T0","leftGain":9,"rightGain":35,"leftArm":9,"rightArm":35,"candidate":34,"gain":25}]- best
42- phase
"combine"- current
"T0"- last
{"id":"T0","leftGain":9,"rightGain":35,"leftArm":9,"rightArm":35,"candidate":34,"gain":25}
- Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
- result
{"present":true,"value":42}
A nonempty optimum stays negative
Input: [-3,-2,-5] · Optional nonempty path sum: {"present":true,"value":-2}
Step 1 of 11: Create explicit postorder continuations.
Stack top is at the right. Child result fields start at zero. A stage-2 frame combines only when it is top again, after both existing children return.
Phase: initial. Current identity: null.
Original objects — unchanged source edges
- T0: -3left → T1right → T2
- T1: -2left → nullright → null
- T2: -5left → nullright → null
Postorder continuations — stack top at right
- T0: stage 0; left 0; right 0
Stage 0 enters left; stage 1 continues into right; stage 2 combines when that frame becomes top again. Child summaries are stored in the parent frame.
Best completed candidate: none yet. Only one arm returns upward; the global candidate may use both nonnegative arms and must include the current node.
Completed-node summaries in the table are teaching history; Java retains only live frames and the scalar best.
Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.
| Variable | Value |
|---|---|
| treeNodes | [{"id":"T0","value":-3,"left":"T1","right":"T2"},{"id":"T1","value":-2,"left":null,"right":null},{"id":"T2","value":-5,"left":null,"right":null}] |
| root | "T0" |
| stack | [{"id":"T0","stage":0,"leftGain":0,"rightGain":0}] |
| summaries | [] |
| best | null |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 public static final class Node { 4 public final int value; 5 public Node left, right; 6 public Node(int value) { this.value = value; } 7 } 8 private static final class Frame { 9 final Node node; 10 int stage; 11 long leftGain, rightGain; 12 Frame(Node node) { this.node = node; } 13 } 14 public static OptionalLong maximumPathSum(Node root) { 15 if (root == null) return OptionalLong.empty(); 16 ArrayDeque<Frame> stack = new ArrayDeque<>(); stack.push(new Frame(root)); 17 long best = Long.MIN_VALUE; 18 while (!stack.isEmpty()) { 19 Frame frame = stack.peek(); 20 if (frame.stage == 0) { 21 frame.stage = 1; 22 if (frame.node.left != null) stack.push(new Frame(frame.node.left)); 23 } else if (frame.stage == 1) { 24 frame.stage = 2; 25 if (frame.node.right != null) stack.push(new Frame(frame.node.right)); 26 } else { 27 long left = Math.max(0L,frame.leftGain), right = Math.max(0L,frame.rightGain); 28 best = Math.max(best,(long) frame.node.value+left+right); 29 long gain = (long) frame.node.value+Math.max(left,right); 30 stack.pop(); 31 if (!stack.isEmpty()) { 32 Frame parent = stack.peek(); 33 if (parent.stage == 1) parent.leftGain = gain; 34 else parent.rightGain = gain; 35 } 36 } 37 } 38 return OptionalLong.of(best); 39 } 40 private static long gain(Node node, long[] best) { 41 if (node == null) return 0; 42 long left = Math.max(0L,gain(node.left,best)), right = Math.max(0L,gain(node.right,best)); 43 best[0] = Math.max(best[0],(long) node.value+left+right); 44 return (long) node.value+Math.max(left,right); 45 } 46 public static OptionalLong baseline(Node root) { 47 if (root == null) return OptionalLong.empty(); 48 long[] best = {Long.MIN_VALUE}; gain(root,best); return OptionalLong.of(best[0]); 49 } 50 } 51
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Create explicit postorder continuations.
Stack top is at the right. Child result fields start at zero. A stage-2 frame combines only when it is top again, after both existing children return.
- treeNodes
[{"id":"T0","value":-3,"left":"T1","right":"T2"},{"id":"T1","value":-2,"left":null,"right":null},{"id":"T2","value":-5,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":0,"leftGain":0,"rightGain":0}]- summaries
[]- best
null- phase
"initial"- current
null
- Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":-3,"left":"T1","right":"T2"},{"id":"T1","value":-2,"left":null,"right":null},{"id":"T2","value":-5,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":1,"leftGain":0,"rightGain":0},{"id":"T1","stage":0,"leftGain":0,"rightGain":0}]- summaries
[]- best
null- phase
"enter-left"- current
"T0"
- Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":-3,"left":"T1","right":"T2"},{"id":"T1","value":-2,"left":null,"right":null},{"id":"T2","value":-5,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":1,"leftGain":0,"rightGain":0},{"id":"T1","stage":1,"leftGain":0,"rightGain":0}]- summaries
[]- best
null- phase
"enter-left"- current
"T1"
- Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":-3,"left":"T1","right":"T2"},{"id":"T1","value":-2,"left":null,"right":null},{"id":"T2","value":-5,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":1,"leftGain":0,"rightGain":0},{"id":"T1","stage":2,"leftGain":0,"rightGain":0}]- summaries
[]- best
null- phase
"enter-right"- current
"T1"
- Combine child results and return one parent-extendable summary.
The global candidate can use two arms, but only one arm is returned upward. A negative node is still a nonempty candidate.
- treeNodes
[{"id":"T0","value":-3,"left":"T1","right":"T2"},{"id":"T1","value":-2,"left":null,"right":null},{"id":"T2","value":-5,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":1,"leftGain":-2,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":-2,"gain":-2}]- best
-2- phase
"combine"- current
"T1"- last
{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":-2,"gain":-2}
- Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":-3,"left":"T1","right":"T2"},{"id":"T1","value":-2,"left":null,"right":null},{"id":"T2","value":-5,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":-2,"rightGain":0},{"id":"T2","stage":0,"leftGain":0,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":-2,"gain":-2}]- best
-2- phase
"enter-right"- current
"T0"
- Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":-3,"left":"T1","right":"T2"},{"id":"T1","value":-2,"left":null,"right":null},{"id":"T2","value":-5,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":-2,"rightGain":0},{"id":"T2","stage":1,"leftGain":0,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":-2,"gain":-2}]- best
-2- phase
"enter-left"- current
"T2"
- Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":-3,"left":"T1","right":"T2"},{"id":"T1","value":-2,"left":null,"right":null},{"id":"T2","value":-5,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":-2,"rightGain":0},{"id":"T2","stage":2,"leftGain":0,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":-2,"gain":-2}]- best
-2- phase
"enter-right"- current
"T2"
- Combine child results and return one parent-extendable summary.
The global candidate can use two arms, but only one arm is returned upward. A negative node is still a nonempty candidate.
- treeNodes
[{"id":"T0","value":-3,"left":"T1","right":"T2"},{"id":"T1","value":-2,"left":null,"right":null},{"id":"T2","value":-5,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":-2,"rightGain":-5}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":-2,"gain":-2},{"id":"T2","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":-5,"gain":-5}]- best
-2- phase
"combine"- current
"T2"- last
{"id":"T2","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":-5,"gain":-5}
- Combine child results and return one parent-extendable summary.
The global candidate can use two arms, but only one arm is returned upward. A negative node is still a nonempty candidate.
- treeNodes
[{"id":"T0","value":-3,"left":"T1","right":"T2"},{"id":"T1","value":-2,"left":null,"right":null},{"id":"T2","value":-5,"left":null,"right":null}]- root
"T0"- stack
[]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":-2,"gain":-2},{"id":"T2","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":-5,"gain":-5},{"id":"T0","leftGain":-2,"rightGain":-5,"leftArm":0,"rightArm":0,"candidate":-3,"gain":-3}]- best
-2- phase
"combine"- current
"T0"- last
{"id":"T0","leftGain":-2,"rightGain":-5,"leftArm":0,"rightArm":0,"candidate":-3,"gain":-3}
- Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
- result
{"present":true,"value":-2}
Path sums exceed int capacity
Input: [2147483647,2147483647,2147483647] · Optional nonempty path sum: {"present":true,"value":6442450941}
Step 1 of 11: Create explicit postorder continuations.
Stack top is at the right. Child result fields start at zero. A stage-2 frame combines only when it is top again, after both existing children return.
Phase: initial. Current identity: null.
Original objects — unchanged source edges
- T0: 2147483647left → T1right → T2
- T1: 2147483647left → nullright → null
- T2: 2147483647left → nullright → null
Postorder continuations — stack top at right
- T0: stage 0; left 0; right 0
Stage 0 enters left; stage 1 continues into right; stage 2 combines when that frame becomes top again. Child summaries are stored in the parent frame.
Best completed candidate: none yet. Only one arm returns upward; the global candidate may use both nonnegative arms and must include the current node.
Completed-node summaries in the table are teaching history; Java retains only live frames and the scalar best.
Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.
| Variable | Value |
|---|---|
| treeNodes | [{"id":"T0","value":2147483647,"left":"T1","right":"T2"},{"id":"T1","value":2147483647,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}] |
| root | "T0" |
| stack | [{"id":"T0","stage":0,"leftGain":0,"rightGain":0}] |
| summaries | [] |
| best | null |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 public static final class Node { 4 public final int value; 5 public Node left, right; 6 public Node(int value) { this.value = value; } 7 } 8 private static final class Frame { 9 final Node node; 10 int stage; 11 long leftGain, rightGain; 12 Frame(Node node) { this.node = node; } 13 } 14 public static OptionalLong maximumPathSum(Node root) { 15 if (root == null) return OptionalLong.empty(); 16 ArrayDeque<Frame> stack = new ArrayDeque<>(); stack.push(new Frame(root)); 17 long best = Long.MIN_VALUE; 18 while (!stack.isEmpty()) { 19 Frame frame = stack.peek(); 20 if (frame.stage == 0) { 21 frame.stage = 1; 22 if (frame.node.left != null) stack.push(new Frame(frame.node.left)); 23 } else if (frame.stage == 1) { 24 frame.stage = 2; 25 if (frame.node.right != null) stack.push(new Frame(frame.node.right)); 26 } else { 27 long left = Math.max(0L,frame.leftGain), right = Math.max(0L,frame.rightGain); 28 best = Math.max(best,(long) frame.node.value+left+right); 29 long gain = (long) frame.node.value+Math.max(left,right); 30 stack.pop(); 31 if (!stack.isEmpty()) { 32 Frame parent = stack.peek(); 33 if (parent.stage == 1) parent.leftGain = gain; 34 else parent.rightGain = gain; 35 } 36 } 37 } 38 return OptionalLong.of(best); 39 } 40 private static long gain(Node node, long[] best) { 41 if (node == null) return 0; 42 long left = Math.max(0L,gain(node.left,best)), right = Math.max(0L,gain(node.right,best)); 43 best[0] = Math.max(best[0],(long) node.value+left+right); 44 return (long) node.value+Math.max(left,right); 45 } 46 public static OptionalLong baseline(Node root) { 47 if (root == null) return OptionalLong.empty(); 48 long[] best = {Long.MIN_VALUE}; gain(root,best); return OptionalLong.of(best[0]); 49 } 50 } 51
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Create explicit postorder continuations.
Stack top is at the right. Child result fields start at zero. A stage-2 frame combines only when it is top again, after both existing children return.
- treeNodes
[{"id":"T0","value":2147483647,"left":"T1","right":"T2"},{"id":"T1","value":2147483647,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":0,"leftGain":0,"rightGain":0}]- summaries
[]- best
null- phase
"initial"- current
null
- Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":2147483647,"left":"T1","right":"T2"},{"id":"T1","value":2147483647,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":1,"leftGain":0,"rightGain":0},{"id":"T1","stage":0,"leftGain":0,"rightGain":0}]- summaries
[]- best
null- phase
"enter-left"- current
"T0"
- Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":2147483647,"left":"T1","right":"T2"},{"id":"T1","value":2147483647,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":1,"leftGain":0,"rightGain":0},{"id":"T1","stage":1,"leftGain":0,"rightGain":0}]- summaries
[]- best
null- phase
"enter-left"- current
"T1"
- Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":2147483647,"left":"T1","right":"T2"},{"id":"T1","value":2147483647,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":1,"leftGain":0,"rightGain":0},{"id":"T1","stage":2,"leftGain":0,"rightGain":0}]- summaries
[]- best
null- phase
"enter-right"- current
"T1"
- Combine child results and return one parent-extendable summary.
The global candidate can use two arms, but only one arm is returned upward. A negative node is still a nonempty candidate.
- treeNodes
[{"id":"T0","value":2147483647,"left":"T1","right":"T2"},{"id":"T1","value":2147483647,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":1,"leftGain":2147483647,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":2147483647,"gain":2147483647}]- best
2147483647- phase
"combine"- current
"T1"- last
{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":2147483647,"gain":2147483647}
- Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":2147483647,"left":"T1","right":"T2"},{"id":"T1","value":2147483647,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":2147483647,"rightGain":0},{"id":"T2","stage":0,"leftGain":0,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":2147483647,"gain":2147483647}]- best
2147483647- phase
"enter-right"- current
"T0"
- Schedule the left child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":2147483647,"left":"T1","right":"T2"},{"id":"T1","value":2147483647,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":2147483647,"rightGain":0},{"id":"T2","stage":1,"leftGain":0,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":2147483647,"gain":2147483647}]- best
2147483647- phase
"enter-left"- current
"T2"
- Schedule the right child after advancing its continuation.
A parent at stage 1 awaits/has received its left child; at stage 2 it awaits/has received its right child. Zero fields represent missing children until real results return.
- treeNodes
[{"id":"T0","value":2147483647,"left":"T1","right":"T2"},{"id":"T1","value":2147483647,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":2147483647,"rightGain":0},{"id":"T2","stage":2,"leftGain":0,"rightGain":0}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":2147483647,"gain":2147483647}]- best
2147483647- phase
"enter-right"- current
"T2"
- Combine child results and return one parent-extendable summary.
The global candidate can use two arms, but only one arm is returned upward. A negative node is still a nonempty candidate.
- treeNodes
[{"id":"T0","value":2147483647,"left":"T1","right":"T2"},{"id":"T1","value":2147483647,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]- root
"T0"- stack
[{"id":"T0","stage":2,"leftGain":2147483647,"rightGain":2147483647}]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":2147483647,"gain":2147483647},{"id":"T2","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":2147483647,"gain":2147483647}]- best
2147483647- phase
"combine"- current
"T2"- last
{"id":"T2","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":2147483647,"gain":2147483647}
- Combine child results and return one parent-extendable summary.
The global candidate can use two arms, but only one arm is returned upward. A negative node is still a nonempty candidate.
- treeNodes
[{"id":"T0","value":2147483647,"left":"T1","right":"T2"},{"id":"T1","value":2147483647,"left":null,"right":null},{"id":"T2","value":2147483647,"left":null,"right":null}]- root
"T0"- stack
[]- summaries
[{"id":"T1","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":2147483647,"gain":2147483647},{"id":"T2","leftGain":0,"rightGain":0,"leftArm":0,"rightArm":0,"candidate":2147483647,"gain":2147483647},{"id":"T0","leftGain":2147483647,"rightGain":2147483647,"leftArm":2147483647,"rightArm":2147483647,"candidate":6442450941,"gain":4294967294}]- best
6442450941- phase
"combine"- current
"T0"- last
{"id":"T0","leftGain":2147483647,"rightGain":2147483647,"leftArm":2147483647,"rightArm":2147483647,"candidate":6442450941,"gain":4294967294}
- Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
- result
{"present":true,"value":6442450941}
Empty input has no path
Input: [] · Optional nonempty path sum: {"present":false}
Step 1 of 2: Create explicit postorder continuations.
Stack top is at the right. Child result fields start at zero. A stage-2 frame combines only when it is top again, after both existing children return.
Phase: initial. Current identity: null.
Original objects — unchanged source edges
Empty tree.
Postorder continuations — stack top at right
Empty.
Stage 0 enters left; stage 1 continues into right; stage 2 combines when that frame becomes top again. Child summaries are stored in the parent frame.
Best completed candidate: none yet. Only one arm returns upward; the global candidate may use both nonnegative arms and must include the current node.
Completed-node summaries in the table are teaching history; Java retains only live frames and the scalar best.
Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.
| Variable | Value |
|---|---|
| treeNodes | [] |
| root | null |
| stack | [] |
| summaries | [] |
| best | null |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 public static final class Node { 4 public final int value; 5 public Node left, right; 6 public Node(int value) { this.value = value; } 7 } 8 private static final class Frame { 9 final Node node; 10 int stage; 11 long leftGain, rightGain; 12 Frame(Node node) { this.node = node; } 13 } 14 public static OptionalLong maximumPathSum(Node root) { 15 if (root == null) return OptionalLong.empty(); 16 ArrayDeque<Frame> stack = new ArrayDeque<>(); stack.push(new Frame(root)); 17 long best = Long.MIN_VALUE; 18 while (!stack.isEmpty()) { 19 Frame frame = stack.peek(); 20 if (frame.stage == 0) { 21 frame.stage = 1; 22 if (frame.node.left != null) stack.push(new Frame(frame.node.left)); 23 } else if (frame.stage == 1) { 24 frame.stage = 2; 25 if (frame.node.right != null) stack.push(new Frame(frame.node.right)); 26 } else { 27 long left = Math.max(0L,frame.leftGain), right = Math.max(0L,frame.rightGain); 28 best = Math.max(best,(long) frame.node.value+left+right); 29 long gain = (long) frame.node.value+Math.max(left,right); 30 stack.pop(); 31 if (!stack.isEmpty()) { 32 Frame parent = stack.peek(); 33 if (parent.stage == 1) parent.leftGain = gain; 34 else parent.rightGain = gain; 35 } 36 } 37 } 38 return OptionalLong.of(best); 39 } 40 private static long gain(Node node, long[] best) { 41 if (node == null) return 0; 42 long left = Math.max(0L,gain(node.left,best)), right = Math.max(0L,gain(node.right,best)); 43 best[0] = Math.max(best[0],(long) node.value+left+right); 44 return (long) node.value+Math.max(left,right); 45 } 46 public static OptionalLong baseline(Node root) { 47 if (root == null) return OptionalLong.empty(); 48 long[] best = {Long.MIN_VALUE}; gain(root,best); return OptionalLong.of(best[0]); 49 } 50 } 51
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Create explicit postorder continuations.
Stack top is at the right. Child result fields start at zero. A stage-2 frame combines only when it is top again, after both existing children return.
- treeNodes
[]- root
null- stack
[]- summaries
[]- best
null- phase
"initial"- current
null
- Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
- result
{"present":false}
Test the contract
Input:
null
Output:OptionalLong.emptyNo nonempty path.
Input:
All-negative values
Output:least-negative valid pathNo empty-zero shortcut.
Input:
[MAX,MAX,MAX]
Output:6442450941Long arithmetic.
Input:
100,000 MAX-valued nodes in a chain
Output:214748364700000Deep wide sum without recursion.
Common mistakes and counterexamples
Initialize the global best to zero
Counterexample: [-3,-2,-5] would incorrectly return an empty zero path.
Require a node in every candidate and start best below all feasible sums.
Return both child arms to the parent
Counterexample: A parent extension then branches at the child.
Propagate one downward arm; use both only for the global candidate.
Accumulate as int
Counterexample: Three MAX nodes exceed int capacity.
Use long fields and cast before adding.
Force the winning path through root
Counterexample: The 42 path in the first example excludes -10.
Track a candidate at every completed node.
Follow-ups
Return the path identities.
Track a downward endpoint with each gain and store both endpoints when best improves. Define ties and reconstruct the unique tree path, charging output size.
Require at least one edge.
A single-node candidate is no longer sufficient. Track whether an arm actually exists and reject empty or leaf-only inputs according to an explicit no-answer contract.
Restrict endpoints to leaves.
Do not clamp an existing mandatory leafward branch to an empty arm. Single-child and all-negative cases require a different recurrence and a precise leaf-to-leaf feasibility rule.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 154/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Related foundations
- Tree foundations: structure, depth, and traversal state
- DFS: traverse components with explicit state meaning