Given an unweighted tree of N nodes , find out the largest distance between any two of its nodes , where distance between two nodes means the number of different edges in the path between two nodes. Note that since it is a tree there will be only one path between any two nodes. Here input is assumed to be given in the following format : For a tree of N vertices, each vertex numbered from 0 to n-1 a vector P will be given where P[i] is the parent of node i. P[i] = -1 shows that i is the root of the tree. Note even if a tree is given in any other form you can create this vector P by just one traversal by storing parent of each node in a vector/array.
Examples :
Input : [-1, 0, 0, 0, 3] Output : 3 Explanation : This is how the tree looks like. 0 / | \ 1 2 3 \ 4 So we can see one of the largest path exists between nodes 1 and 4 and the corresponding path is 1->0->3->4. Length of this path is 3 which is our result printed.
Approach :
We will first create an array disRoot[n] where disRoot[i] is the distance of node i from the root, using the information given to us by the parent array P. Now distance between any two nodes say i and j will be distance of i from node l, plus distance of j from node l, where l is their lowest common ancestor . So distance between i and j can be given by the formula dis = (distance of i from root – distance of l from root) + (distance of j from root – distance of l from root) and distance of any node from root can be found from the disRoot array we already created. So, dis = disRoot[i] – disRoot[l] + disRoot[j] – disRoot[l] i.e. dis = disRoot[i] + disRoot[j] – 2 * disRoot [l]. For n vertices the time complexity of LCA function is O(n) and this function is called for each of the nC2 pair of points so overall time complexity of the given algorithm is O(n^3). Below is the illustration of the above approach:

#include<bits/stdc++.h>
using namespace std;
//function that gives the lowest common ancestor of
//nodes src and dest
int lca(vector<int> &parent,int src,int dest, int n)
{
//hash stores ancestors of src
int hash[n];
//initializing hash
for(int i=0;i<n;i++)
hash[i]=0;
int p1=src,p2=dest;
//p1 also needs to be hashed as p1 itself
//can be ancestor of p2
hash[p1]++;
while(parent[p1]!=-1)
{
hash[parent[p1]]++;
p1=parent[p1];
}
while(parent[p2]!=-1)
{
//this condition holds true if parent[p2]
//is also one of the ancestors of p1
if(hash[parent[p2]]>0)
return parent[p2];
p2=parent[p2];
}
return 0;
}
// main function to give the largest distance between any two nodes
int solve(vector<int> &parent) {
int s=parent.size();
//disRoot stores the distance of each node from root
int disRoot[s];
//max stores maximum distance between two nodes
int max=0;
//following loop constructs disRoot array
for(int i=0;i<s;i++)
{
int dis=0,p=i;
while(parent[p]!=-1)
{
dis++;
p=parent[p];
}
disRoot[i]=dis;
//distance between node i and root
if(dis>max)
max=dis;
}
//following loop checks distance between
//each pair of nodes
for(int i=0;i<s;i++)
{
//this condition is to avoid finding distance of
//each node from root again
if(parent[i]==-1)//that is i is root
continue;
for(int j=i+1;j<s;j++)
{
//find lowest common ancestor of node i and j
int l=lca(parent,i,j,s);
// this condition holds if either of i or j is
//ancestor of other so that case is not considered
//as its distance from root is already considered
if(l==i||l==j)
continue;
//dis is distance between i and j
int dis=disRoot[i]+disRoot[j]-2*disRoot[l];
if(dis>max)
max=dis;
}
}
return(max);
}
//Driver Program
int main()
{
vector <int > P;
P.push_back(-1);
P.push_back(0);
P.push_back(0);
P.push_back(0);
P.push_back(3);
cout<<solve(P);
}
Output : 3