Leetcode 310. Minimum Height Trees

Problem

Leetcode 310 - Minimum Height Tree

Example:

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.

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

Approach

We can use Tropological Sort for the graph, and once there’s only $n \leq{2}$ inside the queue, we can return the result of queue.

Here is the Python code for the solution:

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]
        
        adj = defaultdict(list)
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)
        
        indegree = {}
        leaves = deque()

        for src, nei in adj:
            indegree[src] = len(nei)
            if len(nei) == 1:
                leaves.append(src)
        
        while leaves:
            if n <= 2:
                return list(leaves)
            
            for _ in range(len(leaves)):
                node = leaves.popleft()
                n -= 1
                
                for nei in adj[node]:
                    indegree[nei] -= 1
                    if indegree[nei] == 1:
                        leaves.append(nei)
    

Time Complexity and Space Complexity

Time Complexity: $O(V + E)$

Space Complexity: $O(V)$