Minimum Height Trees

medium graph tree dfs bfs topological sort

Problem

Given a tree with n nodes (n − 1 edges), find every root that minimizes the resulting tree's height. There are at most two such "centroid" roots.

Inputn = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]

Output[3, 4]

edges

def find_min_height_trees(n, edges):
    if n == 1: return [0]
    adj = [set() for _ in range(n)]
    for a, b in edges:
        adj[a].add(b); adj[b].add(a)
    leaves = [i for i in range(n) if len(adj[i]) == 1]
    remaining = n
    while remaining > 2:
        remaining -= len(leaves)
        nxt = []
        for u in leaves:
            v = adj[u].pop()
            adj[v].discard(u)
            if len(adj[v]) == 1: nxt.append(v)
        leaves = nxt
    return leaves

function findMinHeightTrees(n, edges) {
  if (n === 1) return [0];
  const adj = Array.from({ length: n }, () => new Set());
  for (const [a, b] of edges) { adj[a].add(b); adj[b].add(a); }
  let leaves = [];
  for (let i = 0; i < n; i++) if (adj[i].size === 1) leaves.push(i);
  let remaining = n;
  while (remaining > 2) {
    remaining -= leaves.length;
    const nxt = [];
    for (const u of leaves) {
      const v = adj[u].values().next().value;
      adj[u].delete(v);
      adj[v].delete(u);
      if (adj[v].size === 1) nxt.push(v);
    }
    leaves = nxt;
  }
  return leaves;
}

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Arrays.asList(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]); }
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; i++) if (adj.get(i).size() == 1) leaves.add(i);
        int remaining = n;
        while (remaining > 2) {
            remaining -= leaves.size();
            List<Integer> nxt = new ArrayList<>();
            for (int u : leaves) {
                int v = adj.get(u).iterator().next();
                adj.get(v).remove(u);
                if (adj.get(v).size() == 1) nxt.add(v);
            }
            leaves = nxt;
        }
        return leaves;
    }
}

vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
    if (n == 1) return {0};
    vector<unordered_set<int>> adj(n);
    for (auto& e : edges) { adj[e[0]].insert(e[1]); adj[e[1]].insert(e[0]); }
    vector<int> leaves;
    for (int i = 0; i < n; i++) if (adj[i].size() == 1) leaves.push_back(i);
    int remaining = n;
    while (remaining > 2) {
        remaining -= leaves.size();
        vector<int> nxt;
        for (int u : leaves) {
            int v = *adj[u].begin();
            adj[v].erase(u);
            if (adj[v].size() == 1) nxt.push_back(v);
        }
        leaves = nxt;
    }
    return leaves;
}

Explanation

The best root for a minimum-height tree is the center of the tree — and a tree always has either one or two such centers. The clever way to find them is to peel leaves inward, layer by layer, until only the center remains.

We build an adjacency set and collect all current leaves (nodes with degree 1). Then we repeatedly remove this whole layer of leaves at once, which exposes a new layer of leaves underneath, and keep going.

We stop when remaining <= 2 nodes are left. Those 1 or 2 nodes are the centroids — the roots that give the shortest possible height. This works because peeling from both ends of the longest paths meets in the middle.

Removing a leaf u means deleting it from its only neighbor v; if v then drops to degree 1, it becomes a leaf for the next round.

Example: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]. We first peel leaves 0, 1, 2, 5, leaving nodes 3 and 4 in the middle, so the answer is [3, 4].

Time: O(n) Space: O(n)