Last Updated: 5 Jul, 2021

Longest Path in Tree

Moderate
Asked in companies
AmazonCvent

Problem statement

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

Approaches

01 Approach

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.
    • 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.
  • Make an adjacency list tree from the Edges.
  • Set answer as dfs(node, parent, tree).
  • Return answer[0], i.e., the longest path of the tree.

02 Approach

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.

 

Algorithm:

  • 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).
  • Maintain an adjacency list tree from Edges.
  • 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.