LeetCode/Minimum Height Tree

Problem Summary

For an undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, find all roots of the MHTs.

Solution

There is a great analysis on LeetCode:

https://discuss.leetcode.com/topic/30572/share-some-thoughts

I tried a few ways to solve the problem, but mostly ended with TLE (time limit exceeded). Then I read the article mentioned, and felt really inspired.

I realize that it is important to start analyzing the problem from simple cases. For example, consider line graphs before getting to more complicated graphs.

Line graphs look like doubly linked lists. So the root(s) of MHT is the node at the middle of the graph. We can use two pointers to find it. Let each pointer start from one end of the graph and move at the same speed, until they meet or they are next to each other.

With more complex graphs, we need K pointers, if the graph has K leaves(nodes whose degree is 1). We let them move at the same speed towards the center of the graph. When two or more pointers meet, we merge them and keep going. When the pointers meet or are next to each other (in which case there are only two pointers left), we find the root(s).

The process looks like peeling an apple. Or, keep peeling leaves from a “tree”. So when it comes to implementation, we can use topological sort to simulate it.

Plus, there is a little trick with regard to coding. When we iterate through the leaves, we only need to update the information of one node since any leave only connects to one node. That is the difference between Code 1 and Code 2.

Code 1

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int> >& edges) {
        if (n==0)
        	return vector<int>();

        if (edges.size() == 0)
        {
        	if (n == 1)
        		return vector<int>(1,0);
        	else
        		return vector<int>();
        }

        vector<unordered_set<int>> g(n);
        for (int i = 0; i < edges.size(); ++i)
        {
        	int a = edges[i].first, b = edges[i].second;
        	g[a].insert(b);
        	g[b].insert(a);
        }

        vector<int> leaves;
        for (int i = 0; i < n; ++i)
        	if (g[i].size() == 1)
        		leaves.push_back(i);
        
        n -= leaves.size();
        while (n)
        {
        	vector<int> new_leaves;
	       	
	       	for (int i = 0; i < leaves.size(); ++i)
	       	{
	       		int cur = leaves[i];
		       	for (unordered_set<int>::iterator j = g[cur].begin(); j != g[cur].end(); )
	        	{
	        		g[*j].erase(cur);
	        		if (g[*j].size() == 1)
	        		{
	        			new_leaves.push_back(*j);
	        			j = g[cur].erase(j);
	        		}
	        		else
	        			++j;
	        	}	
	       	}
        	leaves = new_leaves;
        	n -= leaves.size();
        }

        return leaves;
    }
};

Code 2

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int> >& edges) {
        if (n==0)
        	return vector<int>();

        if (edges.size() == 0)
        {
        	if (n == 1)
        		return vector<int>(1,0);
        	else
        		return vector<int>();
        }

        vector<unordered_set<int>> g(n);
        for (int i = 0; i < edges.size(); ++i)
        {
        	int a = edges[i].first, b = edges[i].second;
        	g[a].insert(b);
        	g[b].insert(a);
        }

        vector<int> leaves;
        for (int i = 0; i < n; ++i)
        	if (g[i].size() == 1)
        		leaves.push_back(i);
        
        n -= leaves.size();
        while (n)
        {
        	vector<int> new_leaves;
	       	
	       	for (int i = 0; i < leaves.size(); ++i)
	       	{
	       		int cur = leaves[i];

                /* Because cur is a leaf, it is only connected to one other node. */
                unordered_set<int>::iterator j = g[cur].begin();
		       	
	        	g[*j].erase(cur);
	        	if (g[*j].size() == 1)
	        	{
	        		new_leaves.push_back(*j);
	        		g[cur].erase(j);
	        	}
	       	}

        	leaves = new_leaves;
        	n -= leaves.size();
        }

        return leaves;
    }
};