Find the length of the longest path in a binary tree where every node on the path has the same value.
Problem
Given the root of a binary tree, return the number of edges in the longest path such that every node on the path has the same value.
A path may start and end at any two nodes in the tree, but it must always move through parent-child connections and cannot reuse a node.
If no such path exists, the answer is 0.
What to compute
For each node, consider how far a same-value path can extend downward through its left or right child. The final answer is the best path that may pass through some node and combine a matching left chain and right chain.
Input Format
- A binary tree root is provided as the input.
- Each node contains an integer value.
- The tree structure is defined by parent-child links.
Output Format
- Return a single integer: the maximum number of edges in any same-value path.
Constraints
- The tree contains at least 1 node.
- Node values fit in standard 32-bit signed integer range.
- The tree size is small enough for a recursive or iterative DFS solution under typical interview constraints.
Example 1
Input
root = [5,4,5,1,1,null,5]
Output
2
Explanation
The longest same-value path uses the two edges connecting the right-side 5 -> 5 -> 5.
Example 2
Input
root = [1,4,5,4,4,null,5]
Output
2
Explanation
The longest same-value path is the two-edge path from the left child 4 through the root's left subtree: 4 -> 4 -> 4.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.