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.
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.
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.
You do not need to print anything. It has already been taken care of. Just implement the function.
1 <= T <= 5
2 <= N <= 10^5
0 <= Edges[i][0], Edges[i][1] < N
Time limit: 1 sec
In this approach, we find the diameter of the tree recursively using Depth First Search. The diameter of the tree rooted at the current node is either:
The diameter will be the maximum of these two values.
We will try to keep track of maximum and second maximum height among the children node at each node and find the maximum diameter among the children node. The diameter of the current node is the maximum of the sum of the two largest heights and the maximum diameter of children. To implement this, we will create a recursive function dfs(node, parent, tree), where the node is the current node, the parent is the parent node, and the tree is the adjacency list.
Algorithm:
In this approach, we try to find the node at the maximum distance with the root node. The node that is the farthest to the root node must be an endpoint of the longest path (proved by contradiction). Then we find the node with the largest distance from the found node using a breadth-first search.
To implement this, we will create a function maxDistanceNode(startNode, tree), where the parameter startNode is the starting node, and the tree is the adjacency list. This function returns a tuple containing the node furthest from the startNode and the distance between the two nodes.