Roots of the tree having minimum height

The idea is to iterate through all the nodes one by one, select that node as the root of the tree and find the height of the formed tree. We will also maintain a list of nodes that gives the minimum height. Whenever we find a node that gives a minimum height, we will clear our list and that node to the list and update the minimum height that we have found till now. If a node gives the same height as the minimum height, then we will add that node to our output list. Note that we will ignore all nodes that give greater height than minimum height. To find the height of a rooted tree we can use Depth First Search (DFS) or Breadth First Search (BFS).

Steps: 

1. Let 'MIN_HEIGHT' be a variable that stores the minimum height of the tree which we can get. Initialize it as INT_MAX.
2. Let 'ROOT_LIST' be a list of nodes that gives the minimum height.
3. Iterate through ‘i’ = 1 to ‘N’ 
   • Let 'HEIGHT' be the height of the tree rooted at Node i.
   • If 'MIN_HEIGHT' is greater than 'HEIGHT', then
     • Set 'MIN_HEIGHT' as 'HEIGHT'.
     • Clear the 'ROOT_LIST' array
     • Add ‘i’ to the 'ROOT_LIST' array.
   • Otherwise, if 'HEIGHT' is equal to 'MIN_HEIGHT', then
     • Add ‘i’ to the 'ROOT_LIST' array.
4. Return the array 'ROOT_LIST'.

The idea is to observe the fact that all such nodes that give the minimum height when the tree is rooted on it lie on a single path, which is the longest simple path in the tree. It can be seen that for a simple path representing a line tree, it is always optimal to root the tree at the middle of the path to get the minimum height. Similarly, for any tree it is always optimal to root the tree at the middle of the longest path to get minimum height. If the length of the longest path is even, then there will be a single optimal node which will be present in the middle of the path. Otherwise, the two nodes that lie in the middle of the longest path can be used as the root. Therefore, the number of optimal roots are always lesser than or equal to 2.

To find the optimal nodes, we will use an approach similar to Breadth First Search. Initially, we will enqueue all the leaves of the tree into the queue and then in every iteration, we will dequeue all the leaves from the queue and remove all the leaves from the tree, and enqueue all the newly formed leaves into the queue. We will end our algorithm, when the number of elements remaining in the tree are no more than 2. This idea works because the nodes that lie on the middle of the longest path will always be the last nodes to be removed from the queue. Note that, we can simulate the removal of leaf nodes of the tree by keeping track of the degrees of each node.

Steps:

1. Let the array 'ADJ' store the given tree in the adjacency list form, and let the array 'DEGREE' store the degree of each node of the tree.
2. Let ‘Q’ be an empty queue. Insert all leaves of the tree into ‘Q’, leaves of a tree are nodes which have degree equal to 1.
3. Let 'TREE_SIZE' be a variable that stores the number of nodes in the tree. Initialize it as ‘N’.
4. While 'TREE_SIZE' is greater than 2, then
   • Let 'CURR_SIZE' denote the number of elements in the queue.
   • Subtract 'CURR_SIZE' from 'TREE_SIZE' as we will be removing 'CURR_SIZE' leaves from the tree in this iteration.
   • Iterate from ‘i’ = 1 to 'CURR_SIZE'
     • Remove an element from the queue. Let 'CURR_ELEMENT' be the removed element.
     • Iterate through all adjacent nodes of 'CURR_ELEMENT'
       • Let ‘CURR_NEIGHBOUR’ be the current node.
       • Decrease 'DEGREE'[CURR_NEIGHBOUR] by 1. This step works because decreasing the degree of the node by 1 is equivalent to removing one of its adjacent nodes.
       • If 'DEGREE'[CURR_NEIGHBOUR] is equal to 1, then add CURR_NEIGHBOUR into the queue. Here we are checking if the neighbour node after removing one of its adjacent nodes becomes a leaf.
5. Let 'ANS' be the array that stores all the optimal nodes.
6. Insert all elements of the queue into the array 'ANS'.
7. Sort the array 'ANS' and return the sorted array.