Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Problem

Longest Univalue Path

LeetCode #687Medium

Longest chain of equal values

Given the root of a binary tree, return the length, measured in edges, of the longest path where every node along it shares the same value. The path may or may not pass through the root.

Asked atGoogleAmazon

Recursive DFS (post-order arrows + global max)

time O(n)space O(h)

step 1 / 26

binary tree

call stack ↓

(returned)

Recursive DFS (post-order arrows + global max)


▸
1best = 0
2arrow(node):
3    lRaw = arrow(node.left);  rRaw = arrow(node.right)
4    lArm = (left matches)  ? lRaw + 1 : 0
5    rArm = (right matches) ? rRaw + 1 : 0
6    best = max(best, lArm + rArm)      // path bending here
7    return max(lArm, rArm)             // arm for parent
8// answer = best

state

goallongest equal-value path
global best0

line 1The longest univalue path is the longest chain — measured in EDGES — where every node shares the SAME value. Like diameter, it bends at some node. The helper returns the longest equal-value ARROW pointing DOWNWARD from a node: it may only follow a child whose value equals the node's. At each node we glue the left and right arrows together and update a global best.