Complexity Analysis

The time complexity of a single BFS traversal is $O(V + E)$. Since the graph is a tree, $E = V - 1$, so one traversal is $O(N)$. We perform this traversal for every node, resulting in a total time complexity of $O(N^2)$.

Why it Fails

With constraints allowing up to $N = 20,000$, an $O(N^2)$ solution performs roughly $4 \times 10^8$ operations, which exceeds the typical limit of $10^8$ operations per second. This approach will result in a Time Limit Exceeded (TLE) error on large test cases.

Core Insight for Minimum Height Trees

The intuition for the optimal solution comes from analyzing the structure of a tree. The nodes that minimize height are the "centroids" of the tree—the nodes closest to the center.

Consider the longest path in the tree (the diameter). The root of a Minimum Height Tree must be the middle vertex (or vertices) of this longest path. If we root the tree at a leaf node (an endpoint of a path), the height is maximized. Therefore, the optimal roots are as far away from the leaf nodes as possible.

This leads to a "peeling onion" strategy. If we remove all current leaf nodes from the tree, the centroids remain the same, but the tree becomes smaller. We can repeat this process—trimming the outer layer of leaves—until we are left with a core of one or two nodes. These remaining nodes are the roots of the MHTs.

This is structurally identical to Kahn's Algorithm for topological sorting:

1. Invariant: MHT roots are never leaves (unless the tree has $\le 2$ nodes).
2. Process: Identify nodes satisfying a condition (degree 1), process them, and update their neighbors' degrees.
3. Termination: Stop when the remaining nodes count is $\le 2$.

Visual Description: Imagine the tree as a physical structure. The leaves are the outermost layer. In the first iteration of our algorithm, we identify all leaves and "prune" them. This exposes a new layer of nodes that have effectively become leaves in the reduced tree. We repeat this pruning process layer by layer. The pointers move inward from the periphery towards the center. The last batch of nodes remaining in our queue represents the geometric center of the graph.

Algorithm Strategy: Graph BFS - Topological Sort

We implement the solution using a strategy derived from Kahn's Algorithm:

1. Graph Representation: Build an adjacency list to represent the undirected graph.
2. Degree Calculation: Compute the degree (number of connected edges) for every node.
3. Queue Initialization: Initialize a queue with all nodes that have a degree of 1. These are the current leaves.
   • Edge Case: If $N=1$, the single node is the root (degree 0). We handle this separately.
4. Layer-wise Processing:
   • Maintain a count of remaining_nodes, initially set to $N$.
   • While remaining_nodes > 2, perform a level-order traversal (BFS):
     • Determine the number of leaves in the current layer (size).
     • Subtract size from remaining_nodes.
     • For each leaf in the current layer:
       • Remove it (conceptually) by iterating through its neighbors.
       • Decrement the neighbor's degree.
       • If a neighbor's degree becomes 1, it has become a new leaf. Add it to the queue.
5. Result: Once the loop terminates (when $\le 2$ nodes remain), the nodes currently in the queue are the roots of the Minimum Height Trees.

Execution Flow

Let's trace the algorithm with Example 1: n = 4, edges = [[1,0],[1,2],[1,3]].

1. Initialization:

   • Adjacency List: {0: [1], 1: [0, 2, 3], 2: [1], 3: [1]}
   • Degrees: [1, 3, 1, 1] (Node 0 has degree 1, Node 1 has degree 3, etc.)
   • Remaining Nodes: 4

2. Queue Setup:

   • Identify leaves (degree 1): Nodes 0, 2, 3.
   • Queue: [0, 2, 3]

3. Iteration 1:

   • Condition remaining_nodes > 2 is true (4 > 2).
   • Current layer size: 3.
   • Update remaining_nodes: $4 - 3 = 1$.
   • Process Node 0: Neighbor is 1. Decrement degree of 1 from 3 to 2.
   • Process Node 2: Neighbor is 1. Decrement degree of 1 from 2 to 1. Degree is 1, so enqueue 1.
   • Process Node 3: Neighbor is 1. Decrement degree of 1 from 1 to 0.
   • Queue is now: [1].

4. Termination:

   • Condition remaining_nodes > 2 is false (1 is not > 2).
   • Loop ends.

5. Output:

   • Return the contents of the queue: [1].

Proof of Correctness

The correctness relies on the property of the tree diameter. The longest path between any two nodes in a tree is its diameter. The Minimum Height Tree roots must lie at the midpoint of this diameter.

Trimming leaves from the tree is equivalent to removing the endpoints of the diameter. This operation shortens the diameter by 2 (1 from each end) but does not change the midpoint. By repeatedly removing leaves, we continuously shrink the diameter until the midpoint is isolated. Since a path can have at most one or two middle vertices, the algorithm is guaranteed to converge to 1 or 2 nodes.

Reference Implementation

C++ Solution for LeetCode 310

cpp
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) return {0}; // Edge case: single node tree

        vector<vector<int>> adj(n);
        vector<int> degree(n, 0);

        // Build graph and compute degrees
        for (const auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
            degree[edge[0]]++;
            degree[edge[1]]++;
        }

        // Initialize queue with initial leaves
        queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (degree[i] == 1) {
                q.push(i);
            }
        }

        int remaining_nodes = n;
        
        // Trim leaves until 2 or fewer nodes remain
        while (remaining_nodes > 2) {
            int level_size = q.size();
            remaining_nodes -= level_size;
            
            for (int i = 0; i < level_size; ++i) {
                int leaf = q.front();
                q.pop();
                
                for (int neighbor : adj[leaf]) {
                    degree[neighbor]--;
                    if (degree[neighbor] == 1) {
                        q.push(neighbor);
                    }
                }
            }
        }

        vector<int> result;
        while (!q.empty()) {
            result.push_back(q.front());
            q.pop();
        }
        return result;
    }
};

Java Solution for LeetCode 310

java
import java.util.*;

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Collections.singletonList(0);

        // Build graph using adjacency list
        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) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
            degree[edge[0]]++;
            degree[edge[1]]++;
        }

        // Initialize queue with leaves
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                queue.offer(i);
            }
        }

        int remainingNodes = n;

        // Process layers
        while (remainingNodes > 2) {
            int levelSize = queue.size();
            remainingNodes -= levelSize;

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

        return new ArrayList<>(queue);
    }
}

Python Solution for LeetCode 310

python
from collections import deque

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]
            
        # Build adjacency list and degree array
        adj = [[] for _ in range(n)]
        degree = [0] * n
        
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
            degree[u] += 1
            degree[v] += 1
            
        # Initialize queue with all leaf nodes
        queue = deque([i for i in range(n) if degree[i] == 1])
        
        remaining_nodes = n
        
        # Process until we reach the centroid(s)
        while remaining_nodes > 2:
            level_size = len(queue)
            remaining_nodes -= level_size
            
            for _ in range(level_size):
                leaf = queue.popleft()
                
                for neighbor in adj[leaf]:
                    degree[neighbor] -= 1
                    if degree[neighbor] == 1:
                        queue.append(neighbor)
                        
        return list(queue)