Longest path in a tree | Editorial by aksingh007

The problem is to find the longest path in the tree. We can easily understand that the longest path would always be a path between two leaf nodes. So, to solve
this problem what we need is to know a leaf node beforehand and then we can simply find the longest path from that node using BFS. But, there is no hint about 
leaf node from the problem statement. So, we have to take care of this issue on our own. To find the leaf node we would randomly choose a node and start DFS
from that node and find the farthest node from that source node. This can be done using simple DFS. Now, the farthest node would must be a leaf node. There 
could be more than one farthest node. Take any one and start another DFS and print the length of the farthest node. It will suffice.
Basically, we will use 2 DFS, one to locate a leaf node another to find the maximum path length from that node.
**Time Complexity: **O(|V|+|E|) + O(|V|+|E|) =** O(|V|+|E|)**
**Code:**

```
import java.util.*;
import java.io.*;
class Node{
	int next,weight;boolean ispresent;
	Node(int x,int y,boolean p){next=x;weight=y;ispresent=p;}
	Node(int x,int y){next=x;weight=y;ispresent=true;}
}
class Distance implements Comparable<Distance>{
	int vertex,distance;
	Distance(int v,int d){vertex=v;distance=d;}
	public int compareTo(Distance obj){
		return this.distance-obj.distance;
	}
}
@SuppressWarnings("unchecked")
class Graph{
	int N;
	ArrayList<Node> adj[];
	//ArrayList<Edge> edgeList;
	Graph(int n){
		N=n+1;
		adj=new ArrayList[n+1];
		for(int i=0;i<=n;adj[i++]=new ArrayList<Node>());
	}
	void push_edge(int x,int y,int w){
		adj[x].add(0,new Node(y,0));
		adj[y].add(0,new Node(x,0));
	}
	int bfs(int src,boolean done[]){
		HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
		Queue<Integer> queue=new LinkedList<Integer>();
		boolean visited[]=new boolean[N];
		int level[]=new int[N+1];
		level[src]=0;
		queue.offer(src);
		visited[src]=true;
		done[src]=true;
		hm.put(src,-1);
		while(!queue.isEmpty()){
			int cur=queue.poll();
			int lvl=level[cur];
			//if(visited[cur]) continue;
			visited[cur]=true;
			done[cur]=true;
			for(int i=0;i<adj[cur].size();i++){
				int next=adj[cur].get(i).next;
				if(!visited[next]){
					queue.offer(next);
					visited[next]=true;
					done[next]=true;
					hm.put(next,cur);
					level[next]=lvl+1;
				}
			}
		}
		int big=-1;int ans=src;
		for(int i=1;i<N;i++)
		    if(big<level[i]){
		        big=level[i];
		        ans=i;
		    }
		return big;
	}
	int getbfs(int src){
		HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
		Queue<Integer> queue=new LinkedList<Integer>();
		boolean visited[]=new boolean[N];
		int level[]=new int[N+1];
		level[src]=0;
		queue.offer(src);
		visited[src]=true;
		hm.put(src,-1);
		while(!queue.isEmpty()){
			int cur=queue.poll();
			int lvl=level[cur];
			//if(visited[cur]) continue;
			visited[cur]=true;
			for(int i=0;i<adj[cur].size();i++){
				int next=adj[cur].get(i).next;
				if(!visited[next]){
					queue.offer(next);
					visited[next]=true;
					hm.put(next,cur);
					level[next]=lvl+1;
				}
			}
		}
		int big=-1;int ans=src;
		for(int i=1;i<N;i++)
		    if(big<level[i]){
		        big=level[i];
		        ans=i;
		    }
		return ans;
	}
}

class TestClass {
    public static void main(String args[] ) throws Exception {
        //Scanner sc = new Scanner(System.in);
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String nk[]=br.readLine().split(" ");
        
        int n=Integer.parseInt(nk[0]);
        //int arr[]=new int[n+1];
       // int count=0;
        boolean done[]=new boolean[n+1];
        Graph graph=new Graph(n);
        //String aa[]=br.readLine().split(" ");
        
        for(int i=0;i<n-1;i++){
            String uv[]=br.readLine().split(" ");
            int u=Integer.parseInt(uv[0]);
            int v=Integer.parseInt(uv[1]);
            graph.push_edge(u,v,0);
        }
            int leafnode=graph.getbfs(1);
            int temp=graph.bfs(leafnode,done);
            System.out.println(temp);
            return;
        
    }
}

```

Longest path in a tree | Editorial by aksingh007

Download submission

All caught up!

View submission

Is your resume even shortlisted?