Given an undirected tree, how can I find out those vertices which when taken as the root of the tree will minimize the depth of the tree. Similarly, I want to find those vertices which when taken as the root of tree, will maximize the depth of tree. I want to answer this for a general tree in linear time. (Linear in the number of vertices of the tree)

1 Like

Just think about the diameter of the tree and you will find an easy solution in O(N^2) which I believe itâ€™s enough to pass the TL.

Find Diameter of the tree in two passes. Mid points will be the best vertices. then DFS to the farthest nodes(i.e worst nodes). Linear time. O(N^2) will TLE.