static vector<int> findTrees(int nodes, const vector<vector<int>>& edges) {
vector<int> minHeightTreesRootNodes;
//special case
if(nodes == 1) {
minHeightTreesRootNodes.push_back(0);
return minHeightTreesRootNodes;
}
//initialize graph
unordered_map<int, vector<int>> graph;
unordered_map<int, int> inDegree;
for(int i = 0; i < nodes; i++) {
inDegree[i] = 0;
graph[i] = vector<int>();
}
for(int i = 0; i < edges.size(); i++) {
int parent = edges[i][0];
int child = edges[i][1];
graph[parent].push_back(child);
graph[child].push_back(parent);
inDegree[parent]++;
inDegree[child]++;
}
queue<int> leaves;
for(auto entry: inDegree) {
if(entry.second == 1) {
leaves.push(entry.first);
}
}
int currentNodes = nodes;
while(currentNodes > 2) {
int leavesSize = leaves.size();
currentNodes -= leavesSize;
for(int i = 0; i < leavesSize; i++) {
int vtx = leaves.front();
leaves.pop();
vector<int> children = graph[vtx];
for(auto child: children) {
inDegree[child]--;
if(inDegree[child] == 1) {
leaves.push(child);
}
}
}
}
while(leaves.empty() == false) {
minHeightTreesRootNodes.push_back(leaves.front());
leaves.pop();
}
return minHeightTreesRootNodes;
}Hi @Rupinder_Ghotra,
This solution indeed works and it’s using queue instead of dequeue. Thank you for sharing!