Find farthest node from each node in Tree | Add edge between U and V in tree ; Edge from U to V ; Edge from V to U ; DFS to find the first End Node of diameter ; Calculating level of nodes ; Go in opposite direction of parent ; Function to clear the levels of the nodes ; Set all value of lvl [ ] to 0 for next dfs ; Set maximum with 0 ; DFS will calculate second end of the diameter ; Calculating level of nodes ; Store the node with maximum depth from end1 ; Go in opposite direction of parent ; Function to find the distance of the farthest distant node ; Storing distance from end1 to node u ; Function to find the distance of nodes from second end of diameter ; Storing distance from end2 to node u ; Joining Edge between two nodes of the tree ; Find the one end of the diameter of tree ; Find the other end of the diameter of tree ; Find the distance to each node from end1 ; Find the distance to each node from end2 ; Comparing distance between the two ends of diameter ; Driver code ; Function Call
def AddEdge ( u , v ) : NEW_LINE INDENT global adj NEW_LINE adj [ u ] . append ( v ) NEW_LINE adj [ v ] . append ( u ) NEW_LINE DEDENT def findFirstEnd ( u , p ) : NEW_LINE INDENT global lvl , adj , end1 , maxi NEW_LINE lvl [ u ] = 1 + lvl [ p ] NEW_LINE if ( lvl [ u ] > maxi ) : NEW_LINE INDENT maxi = lvl [ u ] NEW_LINE end1 = u NEW_LINE DEDENT for i in range ( len ( adj [ u ] ) ) : NEW_LINE INDENT if ( adj [ u ] [ i ] != p ) : NEW_LINE INDENT findFirstEnd ( adj [ u ] [ i ] , u ) NEW_LINE DEDENT DEDENT DEDENT def clear ( n ) : NEW_LINE INDENT global lvl , dist1 , dist2 NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT lvl [ i ] = 0 NEW_LINE DEDENT maxi = 0 NEW_LINE dist1 [ 0 ] = dist2 [ 0 ] = - 1 NEW_LINE DEDENT def findSecondEnd ( u , p ) : NEW_LINE INDENT global lvl , adj , maxi , end2 NEW_LINE lvl [ u ] = 1 + lvl [ p ] NEW_LINE if ( lvl [ u ] > maxi ) : NEW_LINE INDENT maxi = lvl [ u ] NEW_LINE end2 = u NEW_LINE DEDENT for i in range ( len ( adj [ u ] ) ) : NEW_LINE INDENT if ( adj [ u ] [ i ] != p ) : NEW_LINE INDENT findSecondEnd ( adj [ u ] [ i ] , u ) NEW_LINE DEDENT DEDENT DEDENT def findDistancefromFirst ( u , p ) : NEW_LINE INDENT global dist1 , adj NEW_LINE dist1 [ u ] = 1 + dist1 [ p ] NEW_LINE for i in range ( len ( adj [ u ] ) ) : NEW_LINE INDENT if ( adj [ u ] [ i ] != p ) : NEW_LINE INDENT findDistancefromFirst ( adj [ u ] [ i ] , u ) NEW_LINE DEDENT DEDENT DEDENT def findDistancefromSecond ( u , p ) : NEW_LINE INDENT global dist2 , adj NEW_LINE dist2 [ u ] = 1 + dist2 [ p ] NEW_LINE for i in range ( len ( adj [ u ] ) ) : NEW_LINE INDENT if ( adj [ u ] [ i ] != p ) : NEW_LINE INDENT findDistancefromSecond ( adj [ u ] [ i ] , u ) NEW_LINE DEDENT DEDENT DEDENT def findNodes ( ) : NEW_LINE INDENT global adj , lvl , dist1 , dist2 , end1 , end2 , maxi NEW_LINE n = 5 NEW_LINE AddEdge ( 1 , 2 ) NEW_LINE AddEdge ( 1 , 3 ) NEW_LINE AddEdge ( 3 , 4 ) NEW_LINE AddEdge ( 3 , 5 ) NEW_LINE findFirstEnd ( 1 , 0 ) NEW_LINE clear ( n ) NEW_LINE findSecondEnd ( end1 , 0 ) NEW_LINE findDistancefromFirst ( end1 , 0 ) NEW_LINE findDistancefromSecond ( end2 , 0 ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT x = dist1 [ i ] NEW_LINE y = dist2 [ i ] NEW_LINE if ( x >= y ) : NEW_LINE INDENT print ( end1 , end = " ▁ " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( end2 , end = " ▁ " ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT adj = [ [ ] for i in range ( 10000 ) ] NEW_LINE lvl = [ 0 for i in range ( 10000 ) ] NEW_LINE dist1 = [ - 1 for i in range ( 10000 ) ] NEW_LINE dist2 = [ - 1 for i in range ( 10000 ) ] NEW_LINE end1 , end2 , maxi = 0 , 0 , 0 NEW_LINE findNodes ( ) NEW_LINE DEDENT