Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 5 Jul, 2021

Moderate

```
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:

- Diameter of the any of children node (If the current node is not part of the diameter)
- Sum of the height of two children + 1(current node is part of the diameter )

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**:**

- Make a function
**dfs(node, parent, tree):**This returns an array containing the tree’s diameter rooted at**node**, and height of the**node**.- Initialize two variables
**maxHeight**and**secondMaxHeight**. This will denote the maximum and second maximum height of the child of the**node**. - Set the variables
**currentHeight**and**currentDiameter**as 0. The variable**currentHeight and currentDiameter**store the height and diameter of the current node. - Iterate
**child**through**tree[node]**and call**dfs(child, node, tree)**and get the**childDiameter**and**childHeight.**- Keep track of the maximum and second maximum height of children in
**maxHeight**and**secondMaxHeight**, respectively. **maxChildDiameter**is the maximum value of all**childDiameter.**

- Keep track of the maximum and second maximum height of children in
- Set
**currentHeight**to**maxHeight + 1**. - Value of
**currentDiameter**is the maximum of**maxHeight**+**secondMaxHeight**and**maxChildDiamter** - Return the list containing two integers, i.e.,
**currentDiameter**, and**currentHeight**from the function.

- Initialize two variables
- Make an adjacency list
**tree**from the E**dges**. - Set
**answer**as**dfs(node, parent, tree).** - Return
**answer[0]**, i.e., the longest path of the tree.

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.

- Start at the root node and then do a breadth-first search to find the node with the maximum distance from the root node. This node will be one of the endpoints of the longest path in the graph(can be proved with contradiction).
- After finding one of the endpoints of the longest path, we can see the node at maximum distance from the endpoint found earlier, using another BFS.

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.

- In
**maxDistanceNode(startNode, tree)**:**startNode**is the starting node, and**tree**is the adjacency list. This function returns a tuple containing the node furthest from the**startNode**and the distance between the two nodes.- Create a queue
**q**and a HashMap**distance**. - Push the
**startNode**in the queue and make its distance 0 by making**distance[startNode]**as**0.** - While the queue is not empty, delete the front
**top**and get its distance from**distance[top]**. - Iterate through every child of
**top**which is not in the**distance**and add its distance as**distance[child] = topDistance + 1** - To get the node with maximum distance, iterate through the
**distance**map and find the node with maximum distance. - Return the node maximum distance(
**maxDistanceNode**) and maximum distance (**maxDistance**).

- Create a queue
- Maintain an adjacency list
**tree**from E**dges**. - Set
**list1**as**maxDistanceNode(root, tree)**and**farthestNode**as**list1[0]**. - Set
**list2**as**maxDistanceNode(farthestNode, tree)**. - In the end, we will return the value
**list1[1]**, i.e., the longest path of the tree.