Longest Univalue Path
Measure the longest path, in edges, along which every node holds one and the same value.
Examples
The longest path of value 5 is 5 -> 5 -> 5 (length 2).
Problem Understanding
We need the longest path (edges) where every node has the same value.
Like Diameter, the path does not need to pass through the root. It can form an inverted 'V' shape at any node.
Algorithm Strategy
We use Post-Order DFS.
At each node:
- Recursive calls get the longest univalue path extending down from left and right children.
- Check Value:
- If
node.leftexists andnode.left.val == node.val, we can extend the left path by 1. - Otherwise, the path from the left stops here (RESET to 0).
- Same logic for right child.
- If
- Update Global Max:
maxPath = max(maxPath, arrowLeft + arrowRight). - Return:
max(arrowLeft, arrowRight)(we can only extend one branch up to the parent).
Interactive Visualization
Under each finished node is ↑n, the same-value arrow it returned. A child with a different value gives 0, however long its own arrow was. The longest same-value path found so far is drawn in green.
Dry Run: [5, 4, 5, 1, 1, null, 5]
Tree: [5, 4, 5, 1, 1, null, 5] — root 5 has children 4 and 5; 4 has two children, both 1; the right 5 has a right child 5.
| Node | Left returns | Right returns | Left child same? | Right child same? | arrowLeft | arrowRight | best | Returns |
|---|---|---|---|---|---|---|---|---|
| 1 (left of 4) | 0 | 0 | no child | no child | 0 | 0 | 0 | 0 |
| 1 (right of 4) | 0 | 0 | no child | no child | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 1 ≠ 4 | 1 ≠ 4 | 0 | 0 | 0 | 0 |
| 5 (leaf) | 0 | 0 | no child | no child | 0 | 0 | 0 | 0 |
| 5 (right of root) | 0 | 0 | no child | 5 = 5 | 0 | 1 | 1 | 1 |
| 5 (root) | 0 | 1 | 4 ≠ 5 | 5 = 5 | 0 | 2 | 2 | 2 |
Result: 2 edges, root 5 → right 5 → its right 5.
Edge Cases & Common Mistakes
- Resetting Path: If
node.val != child.val, the path length extending from that child MUST be 0. It's a common mistake to just passleftLenup. - Total Univalue Sum: We are finding path length (edges), not just counting nodes with same value.
- Global Max: Just like Diameter, the longest path might be wholly inside a subtree and never touch the root.
Solution
Post-order traversal with value check.
Longest Univalue Path Code
1var longestUnivaluePath = function(root) {2 let best = 0;34 function arrow(node) {5 if (!node) return 0;6 const left = arrow(node.left);7 const right = arrow(node.right);8 const arrowLeft = node.left && node.left.val === node.val ? left + 1 : 0;9 const arrowRight = node.right && node.right.val === node.val ? right + 1 : 0;10 best = Math.max(best, arrowLeft + arrowRight);11 return Math.max(arrowLeft, arrowRight);12 }1314 arrow(root);15 return best;16};