Roots of the tree having minimum height

New update is available. Click here to update.

Last Updated: 13 Mar, 2021

Roots of the tree having minimum height

Moderate

Solve now

Problem statement

You are given an undirected Tree having 'N' nodes. The nodes are numbered from 1 to 'N'. Your task is to find the sorted list of all such nodes, such that rooting the tree on that node gives the minimum height possible of the given tree.

A tree is a connected acyclic graph. The height of a rooted tree is the maximum value of the distance between the root and all nodes of the tree.

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains an integer, 'N,’ denoting the number of nodes.

The next ‘N’-1 lines of each test case contain two space-separated integers, ‘X’ and ‘Y’ separated by a single space, ‘X’ and ’Y’ denote the two nodes connected by an undirected edge.

Output Format:

For each test case, return the list of all such nodes such that rooting the tree on that node gives the minimum height possible. 

Return all the nodes in a sorted manner.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^5 
1 <= X,Y <= N

The input edges form a tree.

Time limit: 1 sec

Solve now

Approaches

01Approach

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:

Let 'MIN_HEIGHT' be a variable that stores the minimum height of the tree which we can get. Initialize it as INT_MAX.
Let 'ROOT_LIST' be a list of nodes that gives the minimum height.
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.
Return the array 'ROOT_LIST'.

Solve now

02Approach

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:

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.
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.
Let 'TREE_SIZE' be a variable that stores the number of nodes in the tree. Initialize it as ‘N’.
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.
Let 'ANS' be the array that stores all the optimal nodes.
Insert all elements of the queue into the array 'ANS'.
Sort the array 'ANS' and return the sorted array.