# 310. Minimum Height Trees

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, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

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

        0
        |
        1
       / \
      2   3 

Output: [1]

Example 2:

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

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

Output: [3, 4]

# Solution

Approach 1: BFS -- in every iteration, remove nodes with degree == 1 until we have 1 or 2 nodes left. Time: O(N).

Approach 2: the result is the midpoint of the longest path in the graph. To find the longest path in the graph, do a dfs from a random node and find the leaf on the otherside across the longest path, and that leaf is one end of the longest path in the graph. Then dfs from that leaf to find the longest path in the graph.

# Code (Python)

Approach 1:

class Solution:
    def findMinHeightTrees(self, n, edges):
        if n == 1:
            return [0]
        adj_list = [set() for _ in range(n)]
        for edge in edges:
            adj_list[edge[0]].add(edge[1])
            adj_list[edge[1]].add(edge[0])
        nodes_left = n
        leaves = [i for i in range(n) if len(adj_list[i]) == 1] # first level of BFS
        while nodes_left > 2:
            nodes_left -= len(leaves)
            new_leaves = []
            for leave in leaves:
                neighbor = adj_list[leave].pop() # set.pop() pops out a random element from the set
                adj_list[neighbor].remove(leave)
                if len(adj_list[neighbor]) == 1: # only neighbors' degrees are affected
                    new_leaves.append(neighbor)
            leaves = new_leaves
        return leaves

Approach 2:

    def findMinHeightTrees(self, n, edges):
        if n == 1:
            return [0]
        adj_list = [set() for _ in range(n)]
        for edge in edges:
            adj_list[edge[0]].add(edge[1])
            adj_list[edge[1]].add(edge[0])
        global_longest_path = self._longest_path(adj_list, self._longest_path(adj_list, 0)[-1])
        if len(global_longest_path) % 2 == 1:
            return [global_longest_path[len(global_longest_path)//2]]
        else:
            return [global_longest_path[len(global_longest_path)//2-1], global_longest_path[len(global_longest_path)//2]]
    
    def _longest_path(self, adj_list, start):
        longest_path = []
        self._helper([start], adj_list, longest_path)
        return longest_path

    def _helper(self, current_path, adj_list, longest_path):
        if len(adj_list[current_path[-1]]) == 1 and list(adj_list[current_path[-1]])[0] in current_path:
            if not longest_path or len(longest_path) < len(current_path):
                for i in range(len(current_path)):
                    if i < len(longest_path):
                        longest_path[i] = current_path[i]
                    else:
                        longest_path.append(current_path[i])
            return
        for node in adj_list[current_path[-1]]:
            if node not in current_path:
                current_path.append(node)
                self._helper(current_path, adj_list, longest_path)
                current_path.pop()

# Code (C++)

Approach 1:

// BFS
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<unordered_set<int>> link(n, unordered_set<int>());
        for (int i = 0; i < edges.size(); ++i)
        {
            int v1 = edges[i][0];
            int v2 = edges[i][1];
            link[v1].insert(v2);
            link[v2].insert(v1);
        }
        queue<int> q;
        for (int v = 0; v < n; ++v)
        {
            if (link[v].size() <= 1)
                q.push(v);
        }
        vector<int>res;
        int count = 0;
        while (!q.empty())
        {
            if (n - count <= 2) // The result will have at most two nodes.
            {
                while (!q.empty())
                {
                    res.push_back(q.front());
                    q.pop();
                }
                break;
            }
            int qSize = q.size();
            for (int i = 0; i < qSize; ++i)
            {
                int v1 = q.front();
                q.pop();
                count++;
                int v2 = *(link[v1].begin());
                link[v1].erase(v2);
                link[v2].erase(v1);
                if (link[v2].size() == 1)
                    q.push(v2);
            }
        }
        return res;
    }
};

Approach 2:

// DFS - the midpoint of the longest path in the graph.
class Solution {
private:
    vector<unordered_set<int>> link;
    vector<int> longestPath;
    void findLongestPath(vector<int>& path, int start) {
        path.push_back(start);
        if (link[start].size() == 0 && path.size() > longestPath.size())
            longestPath = path;
        for (unordered_set<int>::iterator it = link[start].begin(); it != link[start].end(); ++it)
        {
            link[*it].erase(start);
            findLongestPath(path, *it);
            link[*it].insert(start);
        }
        path.pop_back();
    }
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        link = vector<unordered_set<int>>(n, unordered_set<int>());
        for (int i = 0; i < edges.size(); ++i)
        {
            int v1 = edges[i][0];
            int v2 = edges[i][1];
            link[v1].insert(v2);
            link[v2].insert(v1);
        }
        vector<int> path;
        findLongestPath(path, 0);
        findLongestPath(path, longestPath.back());
        vector<int> res;
        int len = longestPath.size();
        res.push_back(longestPath[len/2]);
        if (len % 2 == 0)
            res.push_back(longestPath[len/2-1]);
        return res;
    }
};