Example 1
ready- Input
root = [ 5, 4, 5, 1, 1, 5 ]- Expected
2- Why
- three connected 5s form a two-edge path
Longest Univalue Path
35 min · longestUnivaluePath()mediumOpen in LeetCode #687 ↗
Matching values can form a road that bends through a parent: one arm arrives from the left, the other leaves through the right.
You're given the root of a binary tree. A univalue path is a path where every node holds the same value. Return the greatest number of edges on any such path.
A few ground rules:
- The path may start and end at any nodes.
- It may join a left arm and a right arm through one node.
- Count edges, not nodes.
- An empty tree and a single-node tree both return
0. - Equal values elsewhere in the tree don't help unless equal-valued edges connect them.
Constraints
0 <= node count <= 10_000-1_000 <= node.val <= 1_000
Hints
Choose a meeting node
At each node, ask how far an equal-valued path can extend down the left and down the right. If both arms match the node, they can be joined.
One arm travels upward
A post-order traversal handles both children before their parent. The path through a node may use both arms, but its parent can continue through only one of them. Return the longer arm upward and keep the joined length in a global best.
Break on a changed value
A child's stored arm counts only when child.val == node.val. Otherwise that side
contributes 0, even if a longer matching path exists deeper in the child subtree.
Follow-up
Could you recover the two endpoint nodes of the longest matching path as well as its length?
Visible cases
Examples
Example 2
ready- Input
root = [ 1, 4, 5, 4, 4, 5 ]- Expected
2- Why
- the best path joins the two 4-valued children
Example 3
ready- Input
root = [ 1 ]- Expected
0- Why
- one node contains no edge
Interview signal
Asked at
AmazonGoogle
Two numbers matter at every node: the best joined path that ends here, and the one arm that can still be offered to the parent.
Repeated arm checks
Treat every node as a possible meeting point. From each matching child, search downward for the longest connected arm with the meeting node's value. Join the left and right arm lengths, then move to the next possible meeting point.
import sys
sys.setrecursionlimit(20_000)
def longest_univalue_path(root: TreeNode | None) -> int:
def arm(node: TreeNode | None, value: int) -> int:
if node is None or node.val != value:
return 0
return 1 + max(arm(node.left, value), arm(node.right, value))
def inspect(node: TreeNode | None) -> int:
if node is None:
return 0
through_node = arm(node.left, node.val) + arm(node.right, node.val)
return max(through_node, inspect(node.left), inspect(node.right))
return inspect(root)arm returns an edge count from the meeting node: the first matching child contributes
1, its matching child contributes another 1, and so on.
Time O(n²) in an all-equal skewed tree because each meeting point scans much of the same suffix again. Space O(h) for recursion.
Post-order arms
Use post-order traversal, which finishes both child subtrees before their parent. Store the longest downward same-value arm for each child. At the parent:
- extend a child's arm by one only when the child value matches;
- join the two extended arms to challenge the global answer;
- store only the longer arm for the parent above.
def longest_univalue_path(root: TreeNode | None) -> int:
if root is None:
return 0
arms: dict[TreeNode, int] = {}
stack = [(root, False)]
best = 0
while stack:
node, expanded = stack.pop()
if expanded:
left_arm = 0
right_arm = 0
if node.left is not None and node.left.val == node.val:
left_arm = 1 + arms[node.left]
if node.right is not None and node.right.val == node.val:
right_arm = 1 + arms[node.right]
best = max(best, left_arm + right_arm)
arms[node] = max(left_arm, right_arm)
continue
stack.append((node, True))
if node.right is not None:
stack.append((node.right, False))
if node.left is not None:
stack.append((node.left, False))
return bestJoining both arms is valid for the answer at this node. Returning both would be invalid:
the parent-to-descendant route can't fork, so only max(left_arm, right_arm) continues.
Time O(n) — constant work after each child finishes. Space O(n) for stored arms and the explicit stack.
The recursive form is shorter and uses O(h) call-stack space, but a 10,000-node line exceeds Python's default recursion limit. The explicit stack covers the full constraint.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
2
Run: visible + custom · Submit: full suite