Largest distance between two nodes of a tree using LCA

Updated

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:

A tree with root 0, children 1, 2 and 3 and node 4 under 3, with the longest path 1, 0, 3, 4 marked and its 3 edges worked out.
#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
Comment
Mithlesh Upadhyay Published 15 Nov 2026 · 4 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials