Problem Statement
For an undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Sample Test Cases
Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]] 0 | 1 / \ 2 3 Output: [1] Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]] 0 1 2 \ | / 3 | 4 | 5 Output: [3, 4]
Problem Solution
Gather all leaves in a queue first. At each iteration, destroy all leaves, destroy the edges that they form in the graph, then add their neighbors to the queue, iff the neighbor is a leaf.
- We initialize a queue of leaf nodes after creating the graph.
- How do we know which are leaf nodes? Keep track of in-degree using an array.
- Now, for the current queue of leaf nodes, we shall remove them from graph, then remove the edges they’re connected to, then update the in-degree of their neighbors.
- After updating the neighbor’s in-degree, see if we can add it into the queue of leaf nodes
- Repeat till we’ve 1 or 2 leaf nodes
Complexity Analysis
Time Complexity: O(n) Because each node will be processed exactly once. They go into the queue of leaves once, and they exit (at most) once.
Space Complexity: Graph creation takes O(E) space ie no of edges to be included.
Code Implementation
#include <bits/stdc++.h> using namespace std; // This class represents a undirected graph using adjacency list class Graph { public: int V; // No. of vertices list<int> *adj; vector<int> degree; Graph(int V); void addEdge(int v, int w); // function to get roots which give minimum height vector<int> rootForMinimumHeight(); }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; for (int i = 0; i < V; i++) degree.push_back(0); } // addEdge method adds vertex to adjacency list and increases // degree by 1 void Graph::addEdge(int v, int w) { adj[v].push_back(w); adj[w].push_back(v); degree[v]++; degree[w]++; } // Method to return roots which gives minimum height to tree vector<int> Graph::rootForMinimumHeight() { queue<int> q; // first enqueue all leaf nodes in queue for (int i = 0; i < V; i++) if (degree[i] == 1) q.push(i); // loop untill total vertex remains less than 2 while (V > 2) { for (int i = 0; i < q.size(); i++) { int t = q.front(); q.pop(); V--; // for each neighbour, decrease its degree and // if it become leaf, insert into queue list<int>::iterator j; for ( j = adj[t].begin(); j != adj[t].end(); j++) { degree[*j]--; if (degree[*j] == 1) q.push(*j); } } } // copying the result from queue to result vector vector<int> res; while (!q.empty()) { res.push_back(q.front()); q.pop(); } return res; } // Driver code to test above methods int main() { Graph g(6); g.addEdge(0, 3); g.addEdge(1, 3); g.addEdge(2, 3); g.addEdge(4, 3); g.addEdge(5, 4); vector<int> res = g.rootForMinimumHeight(); for (int i = 0; i < res.size(); i++) cout << res[i] << " "; cout << endl; }