LC310. Minimum Height Trees

Approach 1: Optimal

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        # Handling the last edge case
        if n == 1:
            return [0]
 
        adj = defaultdict(list)
 
        for n1, n2 in edges:
            adj[n1].append(n2)
            adj[n2].append(n1)
        
        edge_cnt = {}
        leaves = deque()
 
        # Find leaves, i.e, nodes with only one neighbor or one edge.
        # Keep track of edge count for the rest.
        for src, neighbors in adj.items():
            if len(neighbors) == 1:
                leaves.append(src)
            
            edge_cnt[src] = len(neighbors)
        
        while leaves:
            # Given constraints and given graph with no cycles, there can only
            # ever be one or at max two root nodes with minimum height.
            if n <= 2:
                break
            
            # Loop to snap the leaves one by one.
            for i in range(len(leaves)):
                node = leaves.popleft()
 
                # Snapped this leaf so decrement the count
                n -= 1
 
                # Since we snapped this leaf, we should update the edge count of
                # its former neighbors
                for neighbor in adj[node]:
                    edge_cnt[neighbor] -= 1
 
                    # If neighbor's edge count becomes 1, it's become the new leaf
                    # so add it to the queue for next outer loop.
                    if edge_cnt[neighbor] == 1:
                        leaves.append(neighbor)
        
        return list(leaves)

Complexity

Time: TODO
Space: $O(V)$ — where $V$ is number of nodes.

Notes

Given the constraints and given there can be no cycles, the graph can only have at most $2$ root nodes with minimum height and no more.

TODO: Viz

Other Languages