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
tree = { } NEW_LINE path = [ ] NEW_LINE maxHeight , maxHeightNode = - 1 , - 1 NEW_LINE def getDiameterPath ( vertex , targetVertex , parent , path ) : NEW_LINE INDENT if ( vertex == targetVertex ) : NEW_LINE INDENT path . append ( vertex ) NEW_LINE return True NEW_LINE DEDENT for i in range ( len ( tree [ vertex ] ) ) : NEW_LINE INDENT if ( tree [ vertex ] [ i ] == parent ) : NEW_LINE INDENT continue NEW_LINE DEDENT if ( getDiameterPath ( tree [ vertex ] [ i ] , targetVertex , vertex , path ) ) : NEW_LINE INDENT path . append ( vertex ) NEW_LINE return True NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT def farthestNode ( vertex , parent , height ) : NEW_LINE INDENT global maxHeight , maxHeightNode NEW_LINE if ( height > maxHeight ) : NEW_LINE INDENT maxHeight = height NEW_LINE maxHeightNode = vertex NEW_LINE DEDENT if ( vertex in tree ) : NEW_LINE INDENT for i in range ( len ( tree [ vertex ] ) ) : NEW_LINE INDENT if ( tree [ vertex ] [ i ] == parent ) : NEW_LINE INDENT continue NEW_LINE DEDENT farthestNode ( tree [ vertex ] [ i ] , vertex , height + 1 ) NEW_LINE DEDENT DEDENT DEDENT def addedge ( a , b ) : NEW_LINE INDENT if ( a not in tree ) : NEW_LINE INDENT tree [ a ] = [ ] NEW_LINE DEDENT tree [ a ] . append ( b ) NEW_LINE if ( b not in tree ) : NEW_LINE INDENT tree [ b ] = [ ] NEW_LINE DEDENT tree [ b ] . append ( a ) NEW_LINE DEDENT def FindCenter ( n ) : NEW_LINE INDENT maxHeight = - 1 NEW_LINE maxHeightNode = - 1 NEW_LINE farthestNode ( 0 , - 1 , 0 ) NEW_LINE leaf1 = maxHeightNode NEW_LINE maxHeight = - 1 NEW_LINE farthestNode ( maxHeightNode , - 1 , 0 ) NEW_LINE leaf2 = maxHeightNode NEW_LINE path = [ ] NEW_LINE getDiameterPath ( leaf1 , leaf2 , - 1 , path ) NEW_LINE pathSize = len ( path ) NEW_LINE if ( pathSize % 2 == 1 ) : NEW_LINE INDENT print ( path [ int ( pathSize / 2 ) ] * - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( path [ int ( pathSize / 2 ) ] , " , ▁ " , path [ int ( ( pathSize - 1 ) / 2 ) ] , sep = " " , end = " " ) NEW_LINE DEDENT DEDENT N = 4 NEW_LINE tree = { } NEW_LINE addedge ( 1 , 0 ) NEW_LINE addedge ( 1 , 2 ) NEW_LINE addedge ( 1 , 3 ) NEW_LINE FindCenter ( N ) NEW_LINE