Largest Distance Between Two Nodes In A Tree

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
9 upvotes
Asked in companies
WalmartGoogleFacebook

Problem statement

You are given an arbitrary unweighted rooted tree which consists of N nodes, 0 to N - 1. Your task is to find the largest distance between two nodes in the tree.

The distance between two nodes is the number of edges in a path between the nodes (there will always be a unique path between any pair of nodes since it is a tree).

Note : 
Use zero-based indexing for the nodes.

The tree is always rooted at 0.
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The very first line of input contains an integer ‘T’, denoting the number of test cases.

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

The next N-1 lines of each test case contain two space-separated integers u and v, denoting an edge between node u and node v.
Output format : 
For each test case, the largest distance between two nodes in the tree is printed.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.
Follow Up : 
Can you solve this problem in just one traversal?
Constraints : 
1 <= T <= 100 
2 <= N <= 3000
0 <= u , v < N

Time Limit: 1 sec
Sample Input 1 :
1
10
0 1
0 2
0 3
1 4
2 5
2 6
4 7
4 8
6 9
Sample Output 1 :
6
Explanation for sample input 1 :
For the first test case, the tree is shown below. The longest path in the tree is {7, 4, 1, 0, 2, 6, 9} with a length of 6.

Sample 1 - TestCase 1

Sample Input 2 :
1
6
0 1
1 2
1 3
2 4
3 5
Sample Output 2 :
4
Explanation for sample input 2 :
For the first test case, the tree is shown below. The longest path in the tree is {4, 2, 1, 3, 5} with a length of 4.

Sample 2 - TestCase 1

Hint

Find the distance between every pair of nodes in the tree.

Approaches (4)
Brute Force
  • A brute force approach could be to find the distance of each node to every other node in the tree.
  • While doing so, we keep track of the distance of the longest path which can be travelled for each node.
  • The node from which we can travel the maximum distance gives us the answer.

Algorithm:

  • Iterate over the nodes, 0 to N-1.
  • For each node, apply BFS, starting from the current node.
    • Store the distance of the longest path that can be covered from the current node.
  • The maximum of the distances from all the nodes gives us the required answer.

Note:

  • We can also use DFS to calculate the distances between two nodes. But the idea will remain the same.
Time Complexity

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

 

In the worst case, we are traversing the complete tree for every node. Hence, the overall complexity is O(N) * O(N) = O(N ^ 2).

Space Complexity

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

 

In the worst case, extra space is required for the queue.

Code Solution
(100% EXP penalty)
Largest Distance Between Two Nodes In A Tree
Full screen
Console