New update is available. Click here to update.

Longest Path in Tree

Posted: 5 Jul, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given an undirected tree. Your task is to find the longest path in the tree.

The longest path in a tree is defined as the maximum number of edges between any two nodes. You are given a 2-dimensional array ‘Edges’ in which ‘Edges[i][0]’ and ‘Edges[i][1]’ contains an edge.

For Example:
In the example below, the longest path is between nodes 1 and 3. The length of the path is 3 since the number of edges between node 1 and node 3 is 3. Hence, the answer is 3.

altImage

Input Format:
The first line of input contains an integer ‘T’ representing the number of test cases.

The first line of each test case contains an integer ‘N’ representing the number of nodes in the tree.

The following ‘N’ - 1 line of each test case contains two space-separated integers, ‘Edges[i][0]’ and ‘Edges[i][1]’ representing an edge between the two nodes.
Output Format:
For each test case, print a single integer, the length of the longest path in the tree. 

Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the function.
Constraints:
1 <=  T <= 5
2 <= N <= 10^5
0 <= Edges[i][0], Edges[i][1] < N

Time limit: 1 sec