Minimum Height Trees

Problem

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h))  are called minimum height trees (MHTs).

Return a list of all MHTs’ root labels. You can return the answer in any order.

Examples

Example 1:

Input: n = 4, edges = [ [1, 0], [1, 2], [1, 3] ]

Output: [1]

Explanation: As shown below, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

Example 2:

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

Solution

Method 1 - Trimming the leaves

What can be root of MHT? It should be center point of graph. Why? Assume simple graph below, where edges represent chains and vertices represents balls tied to chain:

1 - 2 - 3 - 4 - 5

Now, assume we lift the graph from 1, the height of the tree will be 5:

1
|
2
|
3
|
4
|
5

If we lift tree from 2, the height will be 4:

   2
 /  \
1    3
      \
       4
        \
         5

But if we lift from center, the height will be 3:

     3
   /  \
  2    4
 /      \
1        5

Now, we can have 2 cases:

• Case 1 - Odd Diameter - If the diameter of the tree is odd, the center will be a single node, as we see in above example
• Case 2 - Even Diameter - If the diameter of the tree is even, the center will consist of two adjacent nodes.

So, the root of MHT or center of the graph, will consist of at most 2 nodes. To find such nodes, we can do following:

Algorithm

1. Build the graph in adjacency list representation
2. Identify leaves - leaf node has only 1 node in adjacency list
3. Iteratively removing leaf nodes from the graph while updating their neighbors’ degrees until only one or two centroids remain, revealing the minimum height trees.

This implementation is similar to the BFS topological sort. Remove the leaves, update the degrees of inner vertexes. Then remove the new leaves. Doing so level by level until there are 2 or 1 nodes left. What’s left is our answer!

Code

Java

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
	List<Integer> ans = new ArrayList<>();
	if (n == 1){
		ans.add(0);
		return ans;
	}

	Map<Integer, List<Integer>> graph = new HashMap<>();
	for (int i = 0; i < n; i++) {
		graph.put(i, new ArrayList<>());
	}
	int[] degree = new int[n];

	for (int[] edge: edges) {
		graph.get(edge[0]).add(edge[1]);
		graph.get(edge[1]).add(edge[0]);
		++degree[edge[0]];
		++degree[edge[1]];
	}

	Queue<Integer> leaves = new LinkedList<>();
	for (int i = 0; i < degree.length; i++) {
		if (degree[i] == 1) {
			leaves.offer(i);
		}
	}

	while (!leaves.isEmpty()) {
		List<Integer> currLeaves = new ArrayList<>();
		int size = leaves.size();
		for (int i = 0; i < size; i++) {
			int leaf = leaves.poll();
			currLeaves.add(leaf);
			for (int nei: graph.get(leaf)) {
				--degree[nei];
				if (degree[nei] == 1) {
					leaves.offer(nei);
				}
			}
		}
		ans = currLeaves;
	}
	return ans;
}

Complexity

• Time: O(E + V) where E and V are number edges and vertices. As initially building graph takes O(E) and then as we add neighbours to queue once, taking O(V + E)
• Space: O(V) - as we use extra space for queue leaves and degree array.