Find the node at the center of an N | Java implementation of the above approach ; To create tree ; Function to store the path from given vertex to the target vertex in a vector path ; If the target node is found , push it into path vector ; To prevent visiting a node already visited ; Recursive call to the neighbours of current node inorder to get the path ; Function to obtain and return the farthest node from a given vertex ; If the current height is maximum so far , then save the current node ; Iterate over all the neighbours of current node ; This is to prevent visiting a already visited node ; Next call will be at 1 height higher than our current height ; Function to add edges ; Reset to - 1 ; Reset to - 1 ; Stores one end of the diameter ; Reset the maxHeight ; Stores the second end of the diameter ; Store the diameter into the vector path ; Diameter is equal to the path between the two farthest nodes leaf1 and leaf2 ; Driver code
import java . util . * ; class GFG { static Map < Integer , ArrayList < Integer > > tree ; static ArrayList < Integer > path ; static int maxHeight , maxHeightNode ; static boolean getDiameterPath ( int vertex , int targetVertex , int parent , ArrayList < Integer > path ) { if ( vertex == targetVertex ) { path . add ( vertex ) ; return true ; } for ( Integer i : tree . get ( vertex ) ) { if ( i == parent ) continue ; if ( getDiameterPath ( i , targetVertex , vertex , path ) ) { path . add ( vertex ) ; return true ; } } return false ; } static void farthestNode ( int vertex , int parent , int height ) { if ( height > maxHeight ) { maxHeight = height ; maxHeightNode = vertex ; } if ( tree . get ( vertex ) != null ) for ( Integer i : tree . get ( vertex ) ) { if ( i == parent ) continue ; farthestNode ( i , vertex , height + 1 ) ; } } static void addedge ( int a , int b ) { if ( tree . get ( a ) == null ) tree . put ( a , new ArrayList < > ( ) ) ; tree . get ( a ) . add ( b ) ; if ( tree . get ( b ) == null ) tree . put ( b , new ArrayList < > ( ) ) ; tree . get ( b ) . add ( a ) ; } static void FindCenter ( int n ) { maxHeight = - 1 ; maxHeightNode = - 1 ; farthestNode ( 0 , - 1 , 0 ) ; int leaf1 = maxHeightNode ; maxHeight = - 1 ; farthestNode ( maxHeightNode , - 1 , 0 ) ; int leaf2 = maxHeightNode ; path = new ArrayList < > ( ) ; getDiameterPath ( leaf1 , leaf2 , - 1 , path ) ; int pathSize = path . size ( ) ; if ( pathSize % 2 == 1 ) { System . out . println ( path . get ( pathSize / 2 ) ) ; } else { System . out . println ( path . get ( pathSize / 2 ) + " , ▁ " + path . get ( ( pathSize - 1 ) / 2 ) ) ; } } public static void main ( String [ ] args ) { int N = 4 ; tree = new HashMap < > ( ) ; addedge ( 1 , 0 ) ; addedge ( 1 , 2 ) ; addedge ( 1 , 3 ) ; FindCenter ( N ) ; } }