Find the node at the center of an N | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; map < int , vector < int > > tree ; bool getDiameterPath ( int vertex , int targetVertex , int parent , vector < int > & path ) { if ( vertex == targetVertex ) { path . push_back ( vertex ) ; return true ; } for ( auto i : tree [ vertex ] ) { if ( i == parent ) continue ; if ( getDiameterPath ( i , targetVertex , vertex , path ) ) { path . push_back ( vertex ) ; return true ; } } return false ; } void farthestNode ( int vertex , int parent , int height , int & maxHeight , int & maxHeightNode ) { if ( height > maxHeight ) { maxHeight = height ; maxHeightNode = vertex ; } for ( auto i : tree [ vertex ] ) { if ( i == parent ) continue ; farthestNode ( i , vertex , height + 1 , maxHeight , maxHeightNode ) ; } } void addedge ( int a , int b ) { tree [ a ] . push_back ( b ) ; tree [ b ] . push_back ( a ) ; } void FindCenter ( int n ) { int maxHeight = -1 ; int maxHeightNode = -1 ; farthestNode ( 0 , -1 , 0 , maxHeight , maxHeightNode ) ; int leaf1 = maxHeightNode ; maxHeight = -1 ; farthestNode ( maxHeightNode , -1 , 0 , maxHeight , maxHeightNode ) ; int leaf2 = maxHeightNode ; vector < int > path ; getDiameterPath ( leaf1 , leaf2 , -1 , path ) ; int pathSize = path . size ( ) ; if ( pathSize % 2 ) { cout << path [ pathSize / 2 ] << endl ; } else { cout << path [ pathSize / 2 ] << " , ▁ " << path [ ( pathSize - 1 ) / 2 ] << endl ; } } int main ( ) { int N = 4 ; addedge ( 1 , 0 ) ; addedge ( 1 , 2 ) ; addedge ( 1 , 3 ) ; FindCenter ( N ) ; return 0 ; }