Minimum height roots

JavaView on GFG

Time: O(V+E)

Space: O(V+E)

Problem Overview

Find root(s) of tree that minimize height (minimum height trees).

See our study guide for structured GFG and LeetCode practice.

Intuition

Find root(s) of tree that minimize height (minimum height trees). Topological leaf-trimming.

Algorithm

1Repeatedly remove leaf nodes (degree 1) until 1 or 2 nodes remain. Those are the MHT roots.

Common Pitfalls

• Same as LC 310. At most 2 answers (center of tree). Trim leaves layer by layer like BFS.

Minimum height roots.java

Java

// Approach: Topologically trim leaves repeatedly until 1 or 2 nodes remain. These are the MHT roots.
// Time: O(V+E) Space: O(V+E)
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;
    }
}

Was this solution helpful?