DDSA
Advertisement

Minimum height roots

Minimum height roots.java
Java
import java.util.*;

class Solution {

    public ArrayList<Integer> minHeightRoot(int V, int[][] edges) {
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for (int i = 1; i <= V; i++) {
            adj.add(new ArrayList<>());
        }

        int[] indegree = new int[V];
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            indegree[u]++;
            indegree[v]++;
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 1) {
                q.add(i);
            }
        }

        ArrayList<Integer> result = new ArrayList<>();
        while (V > 2) {
            int size = q.size();
            V -= size;
            while (size > 0) {
                int u = q.remove();
                for (int v : adj.get(u)) {
                    indegree[v]--;
                    if (indegree[v] == 1) {
                        q.add(v);
                    }
                }
                size--;
            }
        }
        while (!q.isEmpty()) {
            result.add(q.remove());
        }

        return result;
    }
}
Advertisement
Was this solution helpful?