Longest Path in Tree

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
2 upvotes
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

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
6
0 1
0 2
2 3
2 4
2 5
Sample Output:
3
Explanation:
The longest path in the given tree is between nodes 1 and 3, and the length of the path is 3. Hence, the answer is 3.

altImage

Sample Input 2:
1
12
0 1
0 2
0 3
1 5
1 6
2 7
3 4
3 9
7 8
9 10
9 11
Sample Output 2:
6
Hint

Find the diameter of the tree.

Approaches (2)
Diameter of Tree

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.
Time Complexity

O(N), where N is the number of nodes in the tree. 

 

There are N nodes and (N - 1) edges in the graph. We are traversing through the graph using Depth First Search. Hence, the overall time complexity becomes O(N + N - 1) = O(N).

Space Complexity

O(N^2), where N is the number of nodes in the given tree.

 

In the worst case, the space complexity O(N^2) is required to create an adjacency list. The space complexity O(N) is required for the recursion stack as there are N recursive calls. Hence, the overall space complexity is O(N^2). 

Code Solution
(100% EXP penalty)
Longest Path in Tree
Full screen
Console