C++: Minimum Height Trees

Thought Process

The solution uses a topological sorting approach to find the center nodes of the tree. We start by identifying all leaf nodes ( nodes with degree 1) and iteratively remove them layer by layer. The key insight is that the Minimum height trees will have roots at the center nodes of the longest path in the tree. We continue this process until we're left with either 1 or 2 nodes, which will be our answer. The algorithm efficiently peels away layers of the tree like an onion until reaching the core. 

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {

        vector<int> adj[n]; // Adjacency List
        vector<int> inDegree(n, 0);
        vector<int> leaves; // Leaf nodes

        // Base case
        if (n == 1) {
            leaves.push_back(0);
            return leaves;
        }

        // Create an adjacency List
        for (int i = 0; i < edges.size(); i++) {

            int u = edges[i][0];
            int v = edges[i][1];

            adj[u].push_back(v);
            adj[v].push_back(u);

            inDegree[u]++;
            inDegree[v]++;
        }

        // If inDegree == 0 then store it as leaves
        for (int i = 0; i < n; i++) {

            if (inDegree[i] == 1)
                leaves.push_back(i);
        }

        // Iterate till we find middle nodes &
        // count of middle nodes can be either 1 or 2
        while (n > 2) {

            n = n - leaves.size();
            vector<int> newLeaves;
            for (int i = 0; i < leaves.size(); i++) {

                int x = leaves[i];
                // For each leaf nodes, reduce the inDegree of its connected
                // nodes by 1.
                for (int j = 0; j < adj[x].size(); j++) {

                    int y = adj[x][j];
                    inDegree[y]--;
                    if (inDegree[y] == 1) {
                        newLeaves.push_back(y);
                    }
                }
            }
            leaves = newLeaves;
        }
        return leaves; // These are the middle nodes which constitute to the MHTs.
    }
};

Code Complexity

Time Complexity: O(n)

Each node and edge is processed exactly once during the topological sorting process.

Space Complexity: O(n)

We use adjacency lists and degree arrays which require linear space relative to the number of nodes.

Code copied!