DSA-082 · Postorder child heights plus a global two-arm edge count

Diameter of Binary Tree

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 23501 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the diameter of a binary tree: the greatest number of edges on any simple path between two nodes. The path may lie wholly below the root.

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 0 for empty and single-node trees. Height summaries count nodes; a path crossing a node has leftHeight+rightHeight edges. All answers fit int under the node bound.

Examples

Input: [1,2,3,4,5]
Output: 3
A longest path is 4–2–1–3, with three edges.
Input: [0,1,null,2,3,4,null,null,5]
Output: 4
The longest path 4–2–1–3–5 crosses node 1, not root 0.

Before you start

Node-count height and edge-count path length
Postorder evaluation using explicit continuation frames

Recognize the structure

A path has a unique highest node. At that node it can use one downward arm from each child, so compute child heights once and maximize their sum across all possible highest nodes.

Try before revealing

Hint 1

Choose the highest node of a candidate path.

Hint 2

You need one best downward arm from each child.

Hint 3

Postorder computes heights once; update a global sum of the two arms at every node.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Recompute heights for each candidate highest node

For every node, recursively compute both child heights, compare their sum, then recursively evaluate both subtrees. For [1,2,3,4,5], heights at root are 2 and 1, producing three edges. Repeated height scans cost O(nh), O(n²) on a chain; keep this compiling baseline to shallow inputs.

Improve the baseline

Suspend a node until both summaries exist

A Frame holds node, stage, leftHeight and rightHeight. Stage 0 schedules left, stage 1 schedules right, and stage 2 combines completed results.

Separate returned summary from global objective

The parent receives height=1+max(leftHeight,rightHeight), a single downward arm. The global best may use both children via leftHeight+rightHeight.

Propagate through the parent’s continuation

After popping a completed frame, parent.stage==1 means the left call just returned; otherwise the right call returned. Assign only that field.

Why it is correct

Postorder frame invariant

Missing child heights start at zero. When a stage-2 frame is top and combines, each existing child has completed with its correct height. A parent may already store stage 2 while its right child is still running above it.

Local path optimum

The longest downward arm in a child has its height in nodes, which equals the number of edges from the current node through that arm. Adding both child heights yields the best path whose highest node is current.

Global completeness

Every simple path has one highest node, which is combined once. Maximizing all local candidates therefore gives the diameter; only heights, not two-arm paths, flow to parents.

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, leftHeight, rightHeight;
        Frame(Node node) { this.node = node; }
    }
    public static int diameter(Node root) {
        if (root == null) return 0;
        ArrayDeque<Frame> stack = new ArrayDeque<>();
        stack.push(new Frame(root));
        int best = 0;
        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 {
                best = Math.max(best,frame.leftHeight+frame.rightHeight);
                int height = 1+Math.max(frame.leftHeight,frame.rightHeight);
                stack.pop();
                if (!stack.isEmpty()) {
                    Frame parent = stack.peek();
                    if (parent.stage == 1) parent.leftHeight = height;
                    else parent.rightHeight = height;
                }
            }
        }
        return best;
    }
    private static int height(Node node) { return node == null ? 0 : 1+Math.max(height(node.left),height(node.right)); }
    public static int baseline(Node root) {
        if (root == null) return 0;
        return Math.max(height(root.left)+height(root.right),Math.max(baseline(root.left),baseline(root.right)));
    }
}

Read the meaningful blocks

Stage is a continuation, not depth

The stack stores suspended computations. Stage 1 can remain active while a whole left subtree runs.

Do not send diameter upward as height

A two-arm path cannot be extended through the parent without branching.

Zero missing-child height is deliberate

A leaf has candidate 0 edges but returns height 1. This prevents the common off-by-one error.

Complexity

The main method processes each node in a constant number of stages: O(n) time and O(h) live frames. It keeps child summaries inside frames rather than an O(n) height map. Output is one int.

The baseline can take O(nh), up to O(n²), and O(h) recursive space. Even a linear-time recursive variant can overflow on the full-depth contract; explicit postorder handles that limit.

Exact-state walkthroughs

Reveal normal and boundary traces

Child heights produce an edge count

Input: [1,2,3,4,5] · Result: 3

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.

Diameter — returned heights and two-arm edge candidates

Phase: initial. Current identity: null.

Original objects — unchanged source edges

T0: 1left → T1right → T2
T1: 2left → T3right → T4
T2: 3left → nullright → null
T3: 4left → nullright → null
T4: 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: 0. Diameter candidates count edges; returned heights count nodes.

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.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]`
root	`"T0"`
stack	`[{"id":"T0","stage":0,"leftHeight":0,"rightHeight":0}]`
summaries	`[]`
best	`0`
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, leftHeight, rightHeight;
11         Frame(Node node) { this.node = node; }
12     }
13     public static int diameter(Node root) {
14         if (root == null) return 0;
15         ArrayDeque<Frame> stack = new ArrayDeque<>();
16         stack.push(new Frame(root));
17         int best = 0;
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                 best = Math.max(best,frame.leftHeight+frame.rightHeight);
28                 int height = 1+Math.max(frame.leftHeight,frame.rightHeight);
29                 stack.pop();
30                 if (!stack.isEmpty()) {
31                     Frame parent = stack.peek();
32                     if (parent.stage == 1) parent.leftHeight = height;
33                     else parent.rightHeight = height;
34                 }
35             }
36         }
37         return best;
38     }
39     private static int height(Node node) { return node == null ? 0 : 1+Math.max(height(node.left),height(node.right)); }
40     public static int baseline(Node root) {
41         if (root == null) return 0;
42         return Math.max(height(root.left)+height(root.right),Math.max(baseline(root.left),baseline(root.right)));
43     }
44 }
45

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":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[]
best
0
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":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[]
best
0
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":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T3","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[]
best
0
phase
"enter-left"
current
"T1"
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":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T3","stage":1,"leftHeight":0,"rightHeight":0}]
summaries
[]
best
0
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":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T3","stage":2,"leftHeight":0,"rightHeight":0}]
summaries
[]
best
0
phase
"enter-right"
current
"T3"
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":1,"rightHeight":0}]
summaries
[{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"candidate":0}]
best
0
phase
"combine"
current
"T3"
last
{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"candidate":0}
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":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":2,"leftHeight":1,"rightHeight":0},{"id":"T4","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"candidate":0}]
best
0
phase
"enter-right"
current
"T1"
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":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":2,"leftHeight":1,"rightHeight":0},{"id":"T4","stage":1,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"candidate":0}]
best
0
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":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":2,"leftHeight":1,"rightHeight":0},{"id":"T4","stage":2,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"candidate":0}]
best
0
phase
"enter-right"
current
"T4"
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":2,"leftHeight":1,"rightHeight":1}]
summaries
[{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0}]
best
0
phase
"combine"
current
"T4"
last
{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0}
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":2,"rightHeight":0}]
summaries
[{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T1","leftHeight":1,"rightHeight":1,"height":2,"candidate":2}]
best
2
phase
"combine"
current
"T1"
last
{"id":"T1","leftHeight":1,"rightHeight":1,"height":2,"candidate":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":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":2,"leftHeight":2,"rightHeight":0},{"id":"T2","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T1","leftHeight":1,"rightHeight":1,"height":2,"candidate":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":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":2,"leftHeight":2,"rightHeight":0},{"id":"T2","stage":1,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T1","leftHeight":1,"rightHeight":1,"height":2,"candidate":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":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":2,"leftHeight":2,"rightHeight":0},{"id":"T2","stage":2,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T1","leftHeight":1,"rightHeight":1,"height":2,"candidate":2}]
best
2
phase
"enter-right"
current
"T2"
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":2,"leftHeight":2,"rightHeight":1}]
summaries
[{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T1","leftHeight":1,"rightHeight":1,"height":2,"candidate":2},{"id":"T2","leftHeight":0,"rightHeight":0,"height":1,"candidate":0}]
best
2
phase
"combine"
current
"T2"
last
{"id":"T2","leftHeight":0,"rightHeight":0,"height":1,"candidate":0}
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":3,"left":null,"right":null},{"id":"T3","value":4,"left":null,"right":null},{"id":"T4","value":5,"left":null,"right":null}]
root
"T0"
stack
[]
summaries
[{"id":"T3","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T1","leftHeight":1,"rightHeight":1,"height":2,"candidate":2},{"id":"T2","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T0","leftHeight":2,"rightHeight":1,"height":3,"candidate":3}]
best
3
phase
"combine"
current
"T0"
last
{"id":"T0","leftHeight":2,"rightHeight":1,"height":3,"candidate":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
3

Winning path lies below root

Input: [0,1,null,2,3,4,null,null,5] · Result: 4

Step 1 of 20: 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.

Diameter — returned heights and two-arm edge candidates

Phase: initial. Current identity: null.

Original objects — unchanged source edges

T0: 0left → T1right → null
T1: 1left → T2right → T3
T2: 2left → T4right → null
T3: 3left → nullright → T5
T4: 4left → nullright → null
T5: 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: 0. Diameter candidates count edges; returned heights count nodes.

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.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]`
root	`"T0"`
stack	`[{"id":"T0","stage":0,"leftHeight":0,"rightHeight":0}]`
summaries	`[]`
best	`0`
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, leftHeight, rightHeight;
11         Frame(Node node) { this.node = node; }
12     }
13     public static int diameter(Node root) {
14         if (root == null) return 0;
15         ArrayDeque<Frame> stack = new ArrayDeque<>();
16         stack.push(new Frame(root));
17         int best = 0;
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                 best = Math.max(best,frame.leftHeight+frame.rightHeight);
28                 int height = 1+Math.max(frame.leftHeight,frame.rightHeight);
29                 stack.pop();
30                 if (!stack.isEmpty()) {
31                     Frame parent = stack.peek();
32                     if (parent.stage == 1) parent.leftHeight = height;
33                     else parent.rightHeight = height;
34                 }
35             }
36         }
37         return best;
38     }
39     private static int height(Node node) { return node == null ? 0 : 1+Math.max(height(node.left),height(node.right)); }
40     public static int baseline(Node root) {
41         if (root == null) return 0;
42         return Math.max(height(root.left)+height(root.right),Math.max(baseline(root.left),baseline(root.right)));
43     }
44 }
45

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":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[]
best
0
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":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[]
best
0
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":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T2","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[]
best
0
phase
"enter-left"
current
"T1"
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":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T2","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T4","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[]
best
0
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":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T2","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T4","stage":1,"leftHeight":0,"rightHeight":0}]
summaries
[]
best
0
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":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T2","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T4","stage":2,"leftHeight":0,"rightHeight":0}]
summaries
[]
best
0
phase
"enter-right"
current
"T4"
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T2","stage":1,"leftHeight":1,"rightHeight":0}]
summaries
[{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0}]
best
0
phase
"combine"
current
"T4"
last
{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0}
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":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T2","stage":2,"leftHeight":1,"rightHeight":0}]
summaries
[{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0}]
best
0
phase
"enter-right"
current
"T2"
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":1,"leftHeight":2,"rightHeight":0}]
summaries
[{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T2","leftHeight":1,"rightHeight":0,"height":2,"candidate":1}]
best
1
phase
"combine"
current
"T2"
last
{"id":"T2","leftHeight":1,"rightHeight":0,"height":2,"candidate":1}
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":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":2,"leftHeight":2,"rightHeight":0},{"id":"T3","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T2","leftHeight":1,"rightHeight":0,"height":2,"candidate":1}]
best
1
phase
"enter-right"
current
"T1"
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":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":2,"leftHeight":2,"rightHeight":0},{"id":"T3","stage":1,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T2","leftHeight":1,"rightHeight":0,"height":2,"candidate":1}]
best
1
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":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":2,"leftHeight":2,"rightHeight":0},{"id":"T3","stage":2,"leftHeight":0,"rightHeight":0},{"id":"T5","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T2","leftHeight":1,"rightHeight":0,"height":2,"candidate":1}]
best
1
phase
"enter-right"
current
"T3"
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":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":2,"leftHeight":2,"rightHeight":0},{"id":"T3","stage":2,"leftHeight":0,"rightHeight":0},{"id":"T5","stage":1,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T2","leftHeight":1,"rightHeight":0,"height":2,"candidate":1}]
best
1
phase
"enter-left"
current
"T5"
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":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":2,"leftHeight":2,"rightHeight":0},{"id":"T3","stage":2,"leftHeight":0,"rightHeight":0},{"id":"T5","stage":2,"leftHeight":0,"rightHeight":0}]
summaries
[{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T2","leftHeight":1,"rightHeight":0,"height":2,"candidate":1}]
best
1
phase
"enter-right"
current
"T5"
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":2,"leftHeight":2,"rightHeight":0},{"id":"T3","stage":2,"leftHeight":0,"rightHeight":1}]
summaries
[{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T2","leftHeight":1,"rightHeight":0,"height":2,"candidate":1},{"id":"T5","leftHeight":0,"rightHeight":0,"height":1,"candidate":0}]
best
1
phase
"combine"
current
"T5"
last
{"id":"T5","leftHeight":0,"rightHeight":0,"height":1,"candidate":0}
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0},{"id":"T1","stage":2,"leftHeight":2,"rightHeight":2}]
summaries
[{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T2","leftHeight":1,"rightHeight":0,"height":2,"candidate":1},{"id":"T5","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T3","leftHeight":0,"rightHeight":1,"height":2,"candidate":1}]
best
1
phase
"combine"
current
"T3"
last
{"id":"T3","leftHeight":0,"rightHeight":1,"height":2,"candidate":1}
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":3,"rightHeight":0}]
summaries
[{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T2","leftHeight":1,"rightHeight":0,"height":2,"candidate":1},{"id":"T5","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T3","leftHeight":0,"rightHeight":1,"height":2,"candidate":1},{"id":"T1","leftHeight":2,"rightHeight":2,"height":3,"candidate":4}]
best
4
phase
"combine"
current
"T1"
last
{"id":"T1","leftHeight":2,"rightHeight":2,"height":3,"candidate":4}
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":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":2,"leftHeight":3,"rightHeight":0}]
summaries
[{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T2","leftHeight":1,"rightHeight":0,"height":2,"candidate":1},{"id":"T5","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T3","leftHeight":0,"rightHeight":1,"height":2,"candidate":1},{"id":"T1","leftHeight":2,"rightHeight":2,"height":3,"candidate":4}]
best
4
phase
"enter-right"
current
"T0"
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":0,"left":"T1","right":null},{"id":"T1","value":1,"left":"T2","right":"T3"},{"id":"T2","value":2,"left":"T4","right":null},{"id":"T3","value":3,"left":null,"right":"T5"},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":5,"left":null,"right":null}]
root
"T0"
stack
[]
summaries
[{"id":"T4","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T2","leftHeight":1,"rightHeight":0,"height":2,"candidate":1},{"id":"T5","leftHeight":0,"rightHeight":0,"height":1,"candidate":0},{"id":"T3","leftHeight":0,"rightHeight":1,"height":2,"candidate":1},{"id":"T1","leftHeight":2,"rightHeight":2,"height":3,"candidate":4},{"id":"T0","leftHeight":3,"rightHeight":0,"height":4,"candidate":3}]
best
4
phase
"combine"
current
"T0"
last
{"id":"T0","leftHeight":3,"rightHeight":0,"height":4,"candidate":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
4

Empty diameter

Input: [] · Result: 0

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.

Diameter — returned heights and two-arm edge candidates

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: 0. Diameter candidates count edges; returned heights count nodes.

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.

State after this step
Variable	Value
treeNodes	`[]`
root	`null`
stack	`[]`
summaries	`[]`
best	`0`
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, leftHeight, rightHeight;
11         Frame(Node node) { this.node = node; }
12     }
13     public static int diameter(Node root) {
14         if (root == null) return 0;
15         ArrayDeque<Frame> stack = new ArrayDeque<>();
16         stack.push(new Frame(root));
17         int best = 0;
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                 best = Math.max(best,frame.leftHeight+frame.rightHeight);
28                 int height = 1+Math.max(frame.leftHeight,frame.rightHeight);
29                 stack.pop();
30                 if (!stack.isEmpty()) {
31                     Frame parent = stack.peek();
32                     if (parent.stage == 1) parent.leftHeight = height;
33                     else parent.rightHeight = height;
34                 }
35             }
36         }
37         return best;
38     }
39     private static int height(Node node) { return node == null ? 0 : 1+Math.max(height(node.left),height(node.right)); }
40     public static int baseline(Node root) {
41         if (root == null) return 0;
42         return Math.max(height(root.left)+height(root.right),Math.max(baseline(root.left),baseline(root.right)));
43     }
44 }
45

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
0
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
0

A leaf has zero edges

Input: [7] · Result: 0

Step 1 of 5: 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.

Diameter — returned heights and two-arm edge candidates

Phase: initial. Current identity: null.

Original objects — unchanged source edges

T0: 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: 0. Diameter candidates count edges; returned heights count nodes.

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.

State after this step
Variable	Value
treeNodes	`[{"id":"T0","value":7,"left":null,"right":null}]`
root	`"T0"`
stack	`[{"id":"T0","stage":0,"leftHeight":0,"rightHeight":0}]`
summaries	`[]`
best	`0`
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, leftHeight, rightHeight;
11         Frame(Node node) { this.node = node; }
12     }
13     public static int diameter(Node root) {
14         if (root == null) return 0;
15         ArrayDeque<Frame> stack = new ArrayDeque<>();
16         stack.push(new Frame(root));
17         int best = 0;
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                 best = Math.max(best,frame.leftHeight+frame.rightHeight);
28                 int height = 1+Math.max(frame.leftHeight,frame.rightHeight);
29                 stack.pop();
30                 if (!stack.isEmpty()) {
31                     Frame parent = stack.peek();
32                     if (parent.stage == 1) parent.leftHeight = height;
33                     else parent.rightHeight = height;
34                 }
35             }
36         }
37         return best;
38     }
39     private static int height(Node node) { return node == null ? 0 : 1+Math.max(height(node.left),height(node.right)); }
40     public static int baseline(Node root) {
41         if (root == null) return 0;
42         return Math.max(height(root.left)+height(root.right),Math.max(baseline(root.left),baseline(root.right)));
43     }
44 }
45

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":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":0,"leftHeight":0,"rightHeight":0}]
summaries
[]
best
0
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":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":1,"leftHeight":0,"rightHeight":0}]
summaries
[]
best
0
phase
"enter-left"
current
"T0"
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":7,"left":null,"right":null}]
root
"T0"
stack
[{"id":"T0","stage":2,"leftHeight":0,"rightHeight":0}]
summaries
[]
best
0
phase
"enter-right"
current
"T0"
Combine child results and return one parent-extendable summary.
Child heights count nodes. Diameter candidates count edges; balance propagates a height only after local certification.
treeNodes
[{"id":"T0","value":7,"left":null,"right":null}]
root
"T0"
stack
[]
summaries
[{"id":"T0","leftHeight":0,"rightHeight":0,"height":1,"candidate":0}]
best
0
phase
"combine"
current
"T0"
last
{"id":"T0","leftHeight":0,"rightHeight":0,"height":1,"candidate":0}
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
0

Test the contract

Input: null or leaf
Output: 0
Diameter counts edges.
Input: Two nodes
Output: 1
One edge.
Input: Diameter entirely below root
Output: 4 in the second example
Global candidate tracking.
Input: 100,000-node chain
Output: 99,999
Linear explicit postorder.

Common mistakes and counterexamples

Return root.leftHeight+root.rightHeight only

Counterexample: The second example has its longest path wholly in the left subtree.

Retain a global maximum over every completed node.

Return leftHeight+rightHeight+1

Counterexample: That counts nodes on the path, not edges.

Use node heights for children and sum them without adding one.

Propagate the two-arm candidate to the parent

Counterexample: It can create a branching walk rather than a simple path.

Return only 1+max(child heights) upward.

Follow-ups

Return the endpoint identities.

Carry a deepest endpoint with each height and store the endpoints when best improves. Define ties explicitly; reconstruct the path with parent information if required.

Use weighted edges.

Height becomes maximum downward edge-weight sum; whether empty arms may be chosen depends on whether a zero-edge path is allowed and whether weights may be negative.

Process a general graph.

A tree’s unique simple paths make two-arm decomposition valid. Cycles invalidate the recurrence; a longest simple path problem in a general graph has substantially different difficulty.

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.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 139/20,000 characters

Self-review

Can I explain the units of every height and candidate?Can I distinguish a parent-extendable arm from a global two-arm path?Can I prove each frame combines only after both children finish?

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform equivalence claims.