DSA problem
Longest Univalue Path
Given the root of a binary tree, return the length of the longest path in the tree such that every node on the path has the same value. The path is counted in edges, not nodes — a path passing through 5 nodes has length 4. The path may or may not pass through the root and is allowed to bend at any node (so it can travel up through a node and then down a different child).
Like Diameter-of-a-Binary-Tree, this problem is solved by a postorder-ish DFS that returns one value to the parent while updating a global maximum. The returned value from dfs(node) is the length of the longest single-direction univalue path starting at node and going down into a child — that is, the longest run of identical values stretching down from node along one side. The trick is that when we are at node, we may combine the down-paths from the left and right children into a single bent path that passes through node, and that combined length is a candidate for the global answer — but we cannot return it upward because a non-straight path cannot be extended further by a parent.
So the recurrence is: recurse on both children to get leftLen and rightLen. If node.left exists and has the same value as node, the left side contributes leftLen + 1; otherwise the left contribution is 0. Similarly for the right. Update globalBest = max(globalBest, leftContrib + rightContrib). Return max(leftContrib, rightContrib) to the caller.
Although the update step happens after the children have been processed (postorder), the overall traversal still walks the tree in the standard preorder/postorder-DFS shape — every node is visited once. Time is O(n); space is O(h) for the recursion stack.
Examples
root = [5,4,5,1,1,null,5]2root = [1,4,5,4,4,null,5]2root = []0Constraints
- The number of nodes in the tree is in the range [0, 10^4].
- -1000 <= Node.val <= 1000
- The depth of the tree will not exceed 1000.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.