Minimum Height Trees . dEexams.com

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [a_i, b_i] indicates that there is an undirected edge between the two nodes a_i and b_i in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).

Return a list of all MHTs' root labels. You can return the answer in any order.

The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Example 1:

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

Example 2:

Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]

Constraints:

1 <= n <= 2 * 10⁴
edges.length == n - 1
0 <= a_i, b_i < n
a_i != b_i
All the pairs (a_i, b_i) are distinct.
The given input is guaranteed to be a tree and there will be no repeated edges.

Solution:

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n <= 2:
            return [x for x in range(n)]
        
        neighbours = {i: [] for i in range(n)}
        
        for e1, e2 in edges:
            neighbours[e1].append(e2)
            neighbours[e2].append(e1)
        
        leaves = []
        
        for neighbour in neighbours:
            if len(neighbours[neighbour]) == 1:
                leaves.append(neighbour)
        
        min_height = n
        
        while min_height > 2:
            min_height -= len(leaves)
            
            tmp = []
            for leaf in leaves:
                for neighbour in neighbours[leaf]:
                    neighbours[neighbour].remove(leaf)
                    if len(neighbours[neighbour]) == 1:
                        tmp.append(neighbour)
            leaves = tmp
        return leaves

Uk01 on Feb 07, 2022 at 08:02 am

If you like dEexams.com and would like to contribute, you can write your article here or mail your article to admin@deexams.com . See your article appearing on the dEexams.com main page and help others to learn.