algoadvance

The problem is to find the roots of the Minimum Height Trees (MHTs) in an undirected graph. A minimum height tree is a tree whose root results in a tree with the minimum possible height.

Given an undirected graph with n nodes labeled from 0 to n-1, and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi, you are required to return a list of all MHTs root labels.

An MHT is defined as a tree whose height is minimized.

Here’s the given constraints:

Clarifying Questions

  1. Is the graph always connected?
  2. Is there any specific expected order for the output?

Assuming answers:

  1. Yes, the graph is connected.
  2. No specific order is required for the output.

Strategy

  1. If there’s only one node (n == 1), return [0].
  2. For other cases, we will use a topological sort approach — essentially, we will trim the leaf nodes (nodes with only one connection) iteratively.
  3. Initially, find all leaf nodes and repeatedly remove them, decreasing the degree of their neighbors. Add new leaf nodes to a queue and repeat the process until 1 or 2 nodes remain (these are the roots of the MHTs).

Steps:

  1. Use an adjacency list to represent the graph.
  2. Collect the initial leaf nodes.
  3. While more than 2 nodes remain, remove leaf nodes layer by layer and update the degree of neighbors.
  4. Finally, the remaining nodes are the roots of the MHTs.

Time Complexity

This approach runs in O(n) time since each edge and node is processed once.

Code

from collections import deque, defaultdict

def findMinHeightTrees(n, edges):
    if n == 1:
        return [0]
    
    # Build the graph with adjacency list
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # Initialize the first layer of leaves
    leaves = [i for i in range(n) if len(graph[i]) == 1]
    
    # Trim the leaves until reaching the centroids
    remaining_nodes = n
    while remaining_nodes > 2:
        remaining_nodes -= len(leaves)
        new_leaves = []
        
        while leaves:
            leaf = leaves.pop()
            neighbor = graph[leaf].pop()
            graph[neighbor].remove(leaf)
            
            if len(graph[neighbor]) == 1:
                new_leaves.append(neighbor)
                
        leaves = new_leaves
    
    return leaves

# Example usage:
print(findMinHeightTrees(4, [[1,0],[1,2],[1,3]]))  # Should return [1]

print(findMinHeightTrees(6, [[3,0],[3,1],[3,2],[3,4],[5,4]]))  # Should return [3, 4]

This method uses a breadth-first search (BFS) like technique tailored to find the centroids of the tree. By repeatedly removing the external layers of the tree (leaf nodes), we eventually narrow down to the central nodes that are the roots of the Minimum Height Trees.

Try our interview co-pilot at AlgoAdvance.com