Largest Distance Between Two Nodes In A Tree

Posted: 15 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
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
Approach 1
  • 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.
Try Problem