Longest Univalue Path is a binary tree problem that tests how well you understand recursion and how information flows upward in a tree. You are given the root of a binary tree, and each node contains an integer value.
Your task is to find the length of the longest path where every node in the path has the same value.
The path does not have to pass through the root. It can start and end at any node in the tree. However, the path must be continuous, meaning it follows parent–child connections. You are not allowed to skip nodes or change direction arbitrarily.
One important detail that often confuses candidates is how the length is measured. The length of the path is counted by the number of edges, not the number of nodes. So a single node by itself contributes a path length of zero.
Why this problem is tricky
At first glance, this looks like a straightforward tree traversal. You might think you can just count how many times the same value appears in a row.
The difficulty is that paths can extend in two directions from a node. A node might connect to a left child with the same value and also to a right child with the same value. In that case, the longest univalue path passes through the node, combining both sides.
At the same time, when returning information to a parent, you are only allowed to extend the path in one direction. This difference between a “global path” and a “return path” is the core challenge of the problem.
Want to explore more coding problem solutions? Check out the Evaluate Division and 3Sum Closest coding problem solutions.
The key idea behind the solution
The clean solution uses depth-first traversal and processes the tree from the bottom up.
For each node, you want to answer a simple question:
“What is the longest downward path starting from this node where all values are equal to this node’s value?”
This downward path can only go to one child, because once you move up to the parent, you cannot branch.
However, while you are at the node, you can also compute a local best path that uses both children, if they match the current node’s value.
That local best is what updates the final answer.
How the recursive logic works
When you visit a node, you first process its left and right children.
Each child returns the length of the longest downward unvalued path starting from that child.
Now you compare the child’s value with the current node’s value.
If the values match, you can extend the child’s path by one edge.
If they do not match, that direction contributes zero to the current node’s univalue path.
You now have two numbers:
a left extension length
a right extension length
The sum of these two values represents the longest univalue path that passes through the current node. This is a candidate for the global maximum.
At the same time, when returning a value to the parent, you return only the maximum of the left or right extension, because a parent can only continue the path in one direction.
This distinction is crucial and is often where mistakes happen.
Why this approach works
Every univalued path in the tree has a “highest” node where the path turns or ends.
By evaluating each node as the potential highest point, you ensure that no valid path is missed.
The recursive return values ensure correct extension upward, while the global maximum ensures the best combined path is recorded.
Each node is processed once, and each decision is made using constant-time checks.
Performance in simple terms
The traversal visits every node exactly one time.
Time complexity is linear in the number of nodes.
Space complexity depends on recursion depth, which is proportional to the height of the tree.
This is efficient and well within interview expectations.
Top comments (0)