Java: 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 List<Integer> findMinHeightTrees(int n, int[][] edges) {
        
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        int[] inDegree = new int[n];

        // Base case
        if(n==1)
            return new ArrayList<>(Arrays.asList(0));

        // Intialization of adjacency list
        for(int i=0;i<n;i++)
            adjList.put(i,new ArrayList<>());

        // Processing edges
        for(int i=0;i<edges.length;i++){

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

            adjList.get(u).add(v);
            adjList.get(v).add(u);
            inDegree[u]++;
            inDegree[v]++;
        }
    
        // Storing all leaves
        List<Integer> leaves = new ArrayList<>();
        for(int i=0;i<n;i++){
            if(inDegree[i]==1)
                leaves.add(i);
        }

        // Starting from the leaves and try to reach the middle of the graph
        // At the end, either one mid node will be there or 2 mid nodes will be there
        // (for odd & even case)
        while(n>2){

            int noOfLeaves = leaves.size();
            n = n-noOfLeaves;
            List<Integer> newLeaves = new ArrayList<>();
            for(int leaf : leaves){
                
                for(int padosi : adjList.get(leaf)){

                    inDegree[padosi]--;
                    if(inDegree[padosi]==1)
                        newLeaves.add(padosi);
                }
            }
            leaves = newLeaves;
        }
        // At the end, nodes corresponding to leafs will be the roots of Min Ht Trees.
        return leaves;
    }
}

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!