Longest Univalue Path
Understanding the Problem
We have a binary tree and need to find the longest path where every node along the path shares the same value. The answer is measured in edges, not nodes, so a path containing 3 nodes with value 5 has length 2.
The path does not have to go strictly downward. It can travel up through a node and back down the other side, forming an inverted-V shape. Consider a node with value 5 that has a left child with value 5 and a right child with value 5. The path goes left-child to parent to right-child, giving length 2.
A path cannot branch. It is a linear sequence of nodes connected by edges, so at any given node the path can extend to at most one child on each side. This forces us to track two different quantities at every node: the longest path passing through the node (which can use both children), and the longest single arm extending downward from the node (which is what we report to the parent above).
Key Constraints:
Number of nodes in [0, 10^4]→ With at most 10,000 nodes, even an O(n^2) solution runs in well under a second, so a brute force passes. O(n) is the target for a clean answer.-1000 <= Node.val <= 1000→ Values fit in a 32-bit integer with room to spare. We only compare parent and child values for equality, so there is no overflow concern even when we add two arm lengths.Depth ≤ 1000→ The tree can be skewed into a chain of 1000 nodes. A recursive solution then needs up to 1000 stack frames, which is within the default stack limit for every language here.- The tree can be empty (0 nodes) → We must handle the null root and return 0.
Approach 1: Brute Force (DFS from Every Node)
Intuition
For every node in the tree, compute the longest univalue path that passes through it. To do that, measure how far the matching values extend downward-left and downward-right from that node. The path through the node is leftArm + rightArm. Taking the maximum over all nodes gives the answer.
This means we traverse the whole tree, and at each node we run a separate helper DFS that measures how deep the matching arms go, tracking the best path found.
The cost is the wasted recomputation. When we measure the downward arm from the root, we explore the entire tree. We then move to the root's left child and explore most of that tree again. For a skewed tree where every value matches, that is O(n) work per node, giving O(n^2) total.
Algorithm
- Traverse every node in the tree using any order (preorder works fine).
- For each node, compute the longest downward univalue arm going left and going right using a helper function.
- The helper function
arrowLength(node, val)returns 0 if the node is null or its value doesn't matchval. Otherwise, it returns 1 + the longer of its own left and right arms (recursing with the same target value). - The path through the current node is
leftArm + rightArm. - Update the global maximum with this path length.
- After visiting all nodes, return the global maximum.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). We visit every node once in the outer traversal. For each node, arrowLength can explore up to O(n) nodes in the worst case (skewed tree where every node has the same value), giving O(n^2) total.
- Space Complexity: O(n). The recursion stack can go up to O(n) deep for a completely skewed tree. For a balanced tree, it would be O(log n).
The repeated recomputation of subtree arms is the bottleneck. The next approach computes every arm once in a single bottom-up pass.
Approach 2: Single DFS with Global Maximum (Optimal)
Intuition
The brute force recomputes each node's downward arm from scratch. Computing every arm once, in a single bottom-up pass, removes that repeated work. We use post-order DFS: process both children first, then the current node. Each recursive call returns the length of the longest univalue arm extending downward from that node.
At every node, we compute two separate quantities:
- The path through this node (for updating the global answer): if both children share the node's value, the path length is leftArm + rightArm. This is the inverted-V shape, and we use it to update the global maximum.
- The arm to return to the parent (for building longer paths higher up): a path cannot fork, so it can only extend in one direction upward. We return the longer of the two matching arms plus 1 for the edge connecting to the parent.
These two quantities differ because of the no-forking rule. The global answer can combine the left and right arms at a node, but only one arm can continue past the node into the parent.
Every univalue path has a single highest node, the point where it bends from going up to going down (or where it starts, if it goes straight down). When dfs processes that highest node, leftPath and rightPath hold the longest matching arms on each side, so leftPath + rightPath equals the full length of that path. Because we run dfs on every node, we evaluate leftPath + rightPath at the highest node of every possible univalue path, and the global maxPath keeps the largest. No path is missed.
Returning max(leftPath, rightPath) rather than the sum is required because a path that continues up into the parent can use only one arm below this node. Returning the sum would let the parent count an arm that bends here and cannot extend further. Resetting an arm to 0 when the child value differs enforces the univalue rule: a broken arm contributes nothing upward.
Algorithm
- Initialize a global variable
maxPath = 0. - Define a recursive function
dfs(node)that returns the longest univalue arm extending downward fromnode. - Base case: if
nodeis null, return 0. - Recursively compute
leftArm = dfs(node.left)andrightArm = dfs(node.right). - If
node.leftexists and has the same value asnode, the left arm extends:leftPath = leftArm + 1. Otherwise,leftPath = 0(the arm breaks). - Same logic for the right side: if
node.rightmatches,rightPath = rightArm + 1, elserightPath = 0. - Update
maxPath = max(maxPath, leftPath + rightPath). This captures the full path through this node using both arms. - Return
max(leftPath, rightPath)to the parent. Only the best single arm can continue upward.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We visit every node exactly once. At each node, we do O(1) work: two comparisons, two additions, and two max operations. Total work is directly proportional to the number of nodes.
- Space Complexity: O(h) where h is the height of the tree. The only space is the recursion stack. For a balanced tree, h = O(log n). For a completely skewed tree, h = O(n).