Find the node at the center of an N | 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
let tree ; let path ; let maxHeight , maxHeightNode ; function getDiameterPath ( vertex , targetVertex , parent , path ) { if ( vertex == targetVertex ) { path . push ( vertex ) ; return true ; } for ( let i = 0 ; i < tree . get ( vertex ) . length ; i ++ ) { if ( tree . get ( vertex ) [ i ] == parent ) continue ; if ( getDiameterPath ( tree . get ( vertex ) [ i ] , targetVertex , vertex , path ) ) { path . push ( vertex ) ; return true ; } } return false ; } function farthestNode ( vertex , parent , height ) { if ( height > maxHeight ) { maxHeight = height ; maxHeightNode = vertex ; } if ( tree . get ( vertex ) != null ) for ( let i = 0 ; i < tree . get ( vertex ) . length ; i ++ ) { if ( tree . get ( vertex ) [ i ] == parent ) continue ; farthestNode ( tree . get ( vertex ) [ i ] , vertex , height + 1 ) ; } } function addedge ( a , b ) { if ( tree . get ( a ) == null ) tree . set ( a , [ ] ) ; tree . get ( a ) . push ( b ) ; if ( tree . get ( b ) == null ) tree . set ( b , [ ] ) ; tree . get ( b ) . push ( a ) ; } function FindCenter ( n ) { maxHeight = - 1 ; maxHeightNode = - 1 ; farthestNode ( 0 , - 1 , 0 ) ; let leaf1 = maxHeightNode ; maxHeight = - 1 ; farthestNode ( maxHeightNode , - 1 , 0 ) ; let leaf2 = maxHeightNode ; path = [ ] ; getDiameterPath ( leaf1 , leaf2 , - 1 , path ) ; let pathSize = path . length ; if ( pathSize % 2 == 1 ) { document . write ( path [ parseInt ( pathSize / 2 , 10 ) ] ) ; } else { document . write ( path [ parseInt ( pathSize / 2 , 10 ) ] + " " + path [ parseInt ( ( pathSize - 1 ) / 2 , 10 ) ] ) ; } } let N = 4 ; tree = new Map ( ) ; addedge ( 1 , 0 ) ; addedge ( 1 , 2 ) ; addedge ( 1 , 3 ) ; FindCenter ( N ) ;