310 Minimum Height Trees

Oct 2022

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 ai 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:

  0         1        2        3
  |       / | \      |        |
  1      0  2  3     1        1
 / \                / \      / \
2   3              0   3    0   2

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:

   3           4
  /|\ \       / \
 0 1 2 4     5   3
       |       / | \
       5      0  1  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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n <= 2:
            return [i for i in range(n)]

        graph = collections.defaultdict(set)
        for n1, n2 in edges:
            graph[n1].add(n2)
            graph[n2].add(n1)
        
        leaves = []
        for i, neighbors in graph.items():
            if len(neighbors) == 1:
                leaves.append(i)
        
        # remove leaves (nodes with only one neighbor)
        # until finding the centroid
        remaining = n
        while remaining > 2:
            remaining -= len(leaves)
            temp_leaves = []
            for leaf in leaves:
                neighbor = graph[leaf].pop()
                graph[neighbor].remove(leaf)
                if len(graph[neighbor]) == 1:
                    temp_leaves.append(neighbor)
            leaves = temp_leaves

        return leaves