Minimum Height Trees

Share

Find all root labels such that the tree has minimum height.

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

Solution Approach

Iteratively remove leaf nodes (degree 1). The remaining 1 or 2 nodes are the centroids.

  • Build adjacency list and track degrees
  • Add all leaves (degree 1) to queue
  • Remove leaves iteratively, updating neighbor degrees
  • When remaining nodes <= 2, stop
  • Return remaining nodes
Java
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    if (n == 1) return Collections.singletonList(0);
    List<Set<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new HashSet<>());
    for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
    Queue<Integer> leaves = new LinkedList<>();
    for (int i = 0; i < n; i++) if (adj.get(i).size() == 1) leaves.add(i);
    int remaining = n;
    while (remaining > 2) {
        int size = leaves.size();
        remaining -= size;
        for (int i = 0; i < size; i++) {
            int leaf = leaves.poll();
            int neighbor = adj.get(leaf).iterator().next();
            adj.get(neighbor).remove(leaf);
            if (adj.get(neighbor).size() == 1) leaves.add(neighbor);
        }
    }
    return new ArrayList<>(leaves);
}
  • Time Complexity: O(n)
  • Space Complexity: O(n)