New update is available. Click here to update.
sidenav-btnClose
Topic list
Longest Univalue Path
MEDIUM
10 mins
286 upvotes
Other topics
Problem solved
Skill meter
Strings
-
Matrices (2D Arrays)
-
Sorting
-
Binary Search
-
Linked List
-
Stacks & Queues
-
Trees
-
Graph
-
Dynamic Programming
-
Greedy
-
Tries
-
Arrays
-
Binary Search Trees
-
Heap
-
Bit Manipulation
-

Longest Univalue Path

Contributed by
Ashwani
Medium
Avg time to solve 10 mins
Success Rate 90 %
Share
286 upvotes

Problem Statement

You are given a binary tree, the task is to find out the length of the longest path which contains nodes with the exact same value. It is not necessary for the path to pass through the root of the binary tree.

Between two nodes, the length of the path can be defined as the number of edges contained between them.

For example, consider the following binary tree:

            7
           / \
          7   7
         / \   \
        8  3    7

For the above tree, the length of the longest path where each node in the path has the same value is 3 and path is 7 -> 7 -> 7 -> 7.

Detailed explanation ( Input/output format, Notes, Constraints, Images )
Sample Input 1:
2
7 7 7 1 1 -1 7 -1 -1 -1 -1 -1 -1
10 3 4 3 3 -1 5 -1 -1 -1 -1 -1 -1
Sample Output 1:
3
2
Explanation of Sample Input 1:
            7
           / \
          7   7
         / \   \
        1  1    7

For the first test case, the length of the longest path where each node in the path has the same value is 3 and path is 7 -> 7 -> 7 -> 7.

            10
           / \
          3   4
         / \   \
        3  3    5

For the second test case, the length of the longest path where each node in the path has the same value is 2 and path is 3 -> 3 -> 3.
Sample Input 2:
2
1 4 5 4 4 -1 5 -1 -1 -1 -1 -1 -1
5 4 5 1 1 -1 5 -1 -1 -1 -1 -1 -1
Sample Output 2:
2
2
Reset Code
Full screen
copy-code
Console