Topological Sort

Minimum Height Trees

You are given a tree represented as an undirected graph, where each node has a unique value between 0 and n-1. The tree is given as a list of edges. You need to find and return all the “root” nodes of the minimum height trees (MHTs).

A Minimum Height Tree is a tree that has the smallest possible height among all possible trees that can be formed with the given nodes and edges.

Table of Contents

Example:

Input:

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

Explanation: The tree representation is as follows:

Output:

[3, 4]

Explanation: The possible minimum height trees are:

Rooted at node 3, the height is 1 (height 1 tree).
Rooted at node 4, the height is 2 (height 2 tree).

Since node 3 and node 4 have the minimum heights among all possible trees, the output is [3, 4].

Time Complexity:

The time complexity of the solution is O(n), where n is the number of nodes in the tree.

Space Complexity:

The space complexity of the solution is O(n), where n is the number of nodes in the tree.

Minimum Height Trees C++ Code:

#include <vector>
#include <unordered_set>
#include <queue>
#include <iostream>

using namespace std;

vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
    if (n == 1) {
        // Special case: Only one node, so it is the minimum height tree.
        return {0};
    }

    // Create adjacency list representation of the graph
    vector<unordered_set<int>> adjList(n);
    for (const auto& edge : edges) {
        adjList[edge[0]].insert(edge[1]);
        adjList[edge[1]].insert(edge[0]);
    }

    queue<int> leaves;
    for (int i = 0; i < n; i++) {
        if (adjList[i].size() == 1) {
            // Leaves have only one neighbor, so we add them to the queue.
            leaves.push(i);
        }
    }

    while (n > 2) {
        int numLeaves = leaves.size();
        n -= numLeaves;

        // Remove the current leaves and their connections from the graph.
        for (int i = 0; i < numLeaves; i++) {
            int leaf = leaves.front();
            leaves.pop();
            int neighbor = *(adjList[leaf].begin());
            adjList[neighbor].erase(leaf);
            if (adjList[neighbor].size() == 1) {
                // After removing the leaf, the neighbor becomes a new leaf.
                leaves.push(neighbor);
            }
        }
    }

    // The remaining nodes in the queue are the roots of the minimum height trees.
    vector<int> result;
    while (!leaves.empty()) {
        result.push_back(leaves.front());
        leaves.pop();
    }

    return result;
}

int main() {
    int n = 6;
    vector<vector<int>> edges = {{3,0},{3,1},{3,2},{3,4},{5,4}};

    vector<int> roots = findMinHeightTrees(n, edges);
    cout << "Root nodes of Minimum Height Trees: ";
    for (int root : roots) {
        cout << root << " ";
    }
    cout << endl;

    return 0;
}

Explanation of Code:

The findMinHeightTrees function is the same as explained earlier. It takes the number of nodes (n) and a vector of edges (edges) as input and returns a vector of integers representing the root nodes of the minimum height trees.
The main function demonstrates the usage of the findMinHeightTrees function with the provided sample input and prints the corresponding output.
In the main function, we define the number of nodes (n) as 6 and initialize the vector edges with the provided sample input.
We then call the findMinHeightTrees function with n and edges as arguments to find the root nodes of the minimum height trees.
Finally, we print the root nodes of the minimum height trees using a loop in the main function.

The output of the program for the given sample input will be:

Root nodes of Minimum Height Trees: 3 4

This means that the possible minimum height trees are rooted at nodes 3 and 4, as they have the minimum heights among all possible trees.

← Alien Dictionary