---

1. Problem Summary

You are given an undirected graph representing a tree with:

• n nodes labeled from 0 to n-1
• edges[i] = [a, b] representing a bidirectional connection

Your task is to return all node labels that can serve as roots of Minimum Height Trees (MHTs).

Important characteristics:

• A tree has no cycles and is connected
• Height is defined as the longest distance from root to any leaf
• There may be one or two valid MHT roots
• If n == 1, the only root is [0]

Example interpretation:
For input:

n = 4
edges = [[1,0],[1,2],[1,3]]

The tree rooted at node 1 has minimum height, so output is:

[1]

---

2. Key Insights

A Minimum Height Tree root lies at the center of the tree

Trees have centroid nodes located in the middle of longest paths.

A tree can have:

• 1 centroid (odd-length diameter)
• 2 centroids (even-length diameter)

Removing leaves layer by layer reveals the centroids

Leaves = nodes with degree 1
When stripped away iteratively:

• Tree shrinks inward
• The last remaining nodes are centroids (MHT roots)

BFS leaf trimming is more efficient than computing height from each node

Naive method → O(n²), too slow
Leaf trimming → O(n)

---

3. Approach

Topological leaf-trimming (BFS)

Steps:

1. Handle special case: if n == 1 → return [0]
2. Build adjacency list and degree count for each node.
3. Initialize a queue with all initial leaves (degree == 1).
4. Track remaining node count.
5. Repeatedly trim leaves:
   • Remove current leaves
   • Decrease degree of neighbors
   • Newly formed leaves enter queue
6. Continue until: remainingNodes <= 2
7. Remaining nodes in queue are MHT roots.

---

4. Time and Space Complexity

Time Complexity: O(n)

Every edge and node processed a constant number of times.

Space Complexity: O(n)

Adjacency list + queue storage.

---

5. Java Solution

import java.util.*;

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {

        if (n == 1) {
            return Collections.singletonList(0);
        }

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        int[] degree = new int[n];

        for (int[] edge : edges) {
            int a = edge[0];
            int b = edge[1];
            adj.get(a).add(b);
            adj.get(b).add(a);
            degree[a]++;
            degree[b]++;
        }

        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                queue.offer(i);
            }
        }

        int remaining = n;

        while (remaining > 2) {
            int size = queue.size();
            remaining -= size;

            for (int i = 0; i < size; i++) {
                int leaf = queue.poll();
                for (int neighbor : adj.get(leaf)) {
                    degree[neighbor]--;
                    if (degree[neighbor] == 1) {
                        queue.offer(neighbor);
                    }
                }
            }
        }

        return new ArrayList<>(queue);
    }
}

---

6. Dry Run Examples

Example 1

Input:

n = 4
edges = [[1,0],[1,2],[1,3]]

Degrees:

0:1, 1:3, 2:1, 3:1

Initial leaves queue:

[0, 2, 3]

Remove leaves:
remaining = 4 – 3 = 1
Node 1 becomes degree 1 → remains

Remaining node:

[1]

Output:

[1]

---

Example 2

Input:

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

Graph centers on 3 and 4

Final result:

[3,4]

---

Example 3

Input:

n = 1
edges = []

Output:

[0]

---

Example 4

Input:

n = 2
edges = [[0,1]]

Both nodes valid

Output:

[0,1]

---

7. Why This Solution Works

• Uses proven centroid property of trees
• Avoids computing height repeatedly
• Shrinks graph layer by layer
• Remaining nodes always correspond to MHT roots
• Works for large n efficiently

---

8. Common Mistakes

1. Trying BFS/DFS height calculation from every node (too slow)
2. Forgetting special case when n = 1
3. Mismanaging degree decrement
4. Assuming only one root always exists
5. Treating graph as directed instead of undirected