687 · Longest Univalue Path

LC 543's skeleton with an equality guard on each edge. Pure rep of the record/return split — the only new idea is that a branch contributes 0 when the edge into it breaks the value.

○ optional rep for sub-variant C

1 — The problem

Find the longest path along which every node has the same value, measured in edges. The path need not pass through the root.

Structurally identical to the diameter: return the longest same-valued path going down from here, record the longest one that turns here. The one addition is that each child's contribution is admitted only if the edge to it connects equal values:

	543. Diameter	687. Univalue Path
Left arm	`L + 1`, always	`L + 1` if `nd.left.val == nd.val`, else 0
Recorded	`L + R`	`left + right` — same
Returned	`1 + max(L, R)`	`max(left, right)` — same

Compare with LC 124, where the clamp max(0, child) plays the identical role: a branch that does not help contributes nothing rather than being excluded by a special case. The gate is different, the shape is the same.

2 — A guard on every edge

The answer is 2, along the three 5s down the right. Watch the root: its left child is a 4, so that arm is gated to 0 even though the subtree below it is perfectly valid on its own terms.

Both children must still be recursed into unconditionally — line 3 runs before the guards. A subtree whose top value differs from yours may still contain the global best somewhere inside it, and skipping it would miss that. The guard controls what you inherit, not what you visit.

2.1 The two bugs this problem is for

Mistake	Symptom
Skipping the recursion when the values differ — `if (nd.left.val == nd.val) L = arrow(nd.left);`	Whole subtrees never explored. Wrong whenever the answer lies under a value change, which is the common case.
Returning `1 + max(left, right)`, copying 543 too literally	Off by one everywhere. Here the `+1` already lives inside the guards, because it is paid per accepted edge, not per node.

The second is the more instructive one. In 543 every edge counts, so the increment can live at the node; here edges are conditional, so the increment has to move to where the condition is tested.

3 — Complexity and edge cases

Time O(n), space O(h). One postorder pass.
Empty tree: 0.
Single node: 0 — a path of one node has no edges.
All values equal: the answer is the tree's diameter, and the two problems coincide exactly. Good check that the guards are transparent when they never fire.
All values distinct: 0. Every guard fails, every arm is 0.
The answer does not touch the root in the visualizer's tree — the same property LC 543 is built around, and the reason the maximum must be recorded rather than returned.
Common bug: initialising best inside the helper, so it resets on every call.

4 — Reference implementation

Java 21Edge-gated arms with a recorded maximum, matching the visualizer.14 lines

private int best;

public int longestUnivaluePath(TreeNode root) {
    best = 0;
    arrow(root);
    return best;
}

private int arrow(TreeNode nd) {
    if (nd == null) return 0;
    int L = arrow(nd.left);       // always recurse — the guard is about inheriting
    int R = arrow(nd.right);
    int left = 0, right = 0;
    if (nd.left  != null && nd.left.val  == nd.val) left  = L + 1;
    if (nd.right != null && nd.right.val == nd.val) right = R + 1;
    best = Math.max(best, left + right);   // record: turns here
    return Math.max(left, right);       // return: continues up
}