Minimum Height Trees - Leetcode Solution

Minimum Height Trees is a graph problem in which we are given a undirected graph with n vertices and n-1 edges. We need to find a set of nodes that form the root of a tree such that the height of the tree is minimized. The resulting tree must span all n nodes in the graph. If there are multiple answers, we need to return any of them.

The approach to solve this problem is to use a BFS-based topo-sort of the vertices. First, we need to construct the graph using an adjacency list. Then, for every vertex v in the graph, we need to find the number of connections it has. This information will help us to identify the leaf vertices in the graph, which are vertices with only one connection.

We will then remove all leaf vertices from the graph and the new graph we get will have new leaf nodes, as well as new internal nodes. We repeat this process until we are left with only one or two nodes in the graph.

If we have only one node in the graph, it is the root of the minimum height tree. If we have two nodes in the graph, they are the roots of the minimum height trees.

Here is the implementation of the above-mentioned approach:

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) return vector<int>{0};
        vector<vector<int>> adj(n);
        vector<int> degree(n, 0);
        for (auto e : edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
            degree[e[0]]++;
            degree[e[1]]++;
        }
        queue<int> leaves;
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) leaves.push(i);
        }

        while (n > 2) {
            int size = leaves.size();
            n -= size;
            for (int i = 0; i < size; i++) {
                int leaf = leaves.front();
                leaves.pop();
                for (int neighbor : adj[leaf]) {
                    if (--degree[neighbor] == 1) leaves.push(neighbor);
                }
            }
        }

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

Time Complexity: O(N), where N is the number of nodes in the graph, as we visit each node once.

Space Complexity: O(N), as we are storing the adjacency list and the degree vector for each node.

1