310 Minimum Height Trees

For a 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:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3
return [1]

Example 2:

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

     0  1  2
      \ | /
        3
        |
        4
        |
        5
return [3, 4]

Note:

(1) According to the definition of tree on Wikipedia: “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.”

(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Naive Approach:

The Idea: For every node in the tree, find the height of that node. Store these into a dictionary. Sort by height and return the smallest homogenious group. The program below is a bit unconventional using this idea because I was initially trying to find an optimal solution.

Complexity: O(n^2) time and O(n) space

import queue
import operator

class Solution:
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """

        if not n:
            return []

        g = {i:set() for i in range(0, n)}
        for s, e in edges:
            g[s].add(e)
            g[e].add(s)

        g_heights = {}
        def BFS_heights(root):
            visited = set()
            q = queue.Queue()
            q.put((root, 0))

            while not q.empty():
                node, height = q.get()
                g_heights[node] = height
                visited.add(node)

                for neighbor in g[node]:
                    if neighbor not in visited:
                        q.put((neighbor, height + 1))

        leafs = []
        def id_leafs(root, visited):
            visited.add(root)
            if len(g[root]) == 1:
                leafs.append(root)
            for neighbor in g[root]:
                if neighbor not in visited:
                    id_leafs(neighbor, visited)

        id_leafs(0, set())

        MHTs = {node:float('-inf') for node in range(0, n)}
        for node in range(0, n):
            BFS_heights(node)
            for leaf in leafs:
                MHTs[node] = max(MHTs[node], abs(g_heights[leaf] - g_heights[node]))

        MHTs_list = sorted(MHTs.items(), key=operator.itemgetter(1))
        sol = []
        for node, height in MHTs_list:
            if height == MHTs_list[0][1]:
                sol.append(node)
            else:
                break

        return sol

sol = Solution()
print(sol.findMinHeightTrees(n = 6,
                             edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]))

Linear Time:

The Idea: From a high level, first find all the leafs, remove them from the tree and continue this process until you have 2 or fewer nodes remaining. Because we are iterating from all the leafs to the middle of the tree, the distance is minimized from the original leaves. The graphic below shows this process. First lets get some intuition as to why there can only be a maximum of two MHTs. This can be formally proved through induction, but lets just get the general idea here. First understand that every step in the graphic below is an independent tree. Athough they have all derived from one another, each tree is an independent subproblem. Now lets consider the few base conditions. If we have 3 nodes in a tree, there will always be 2 leafs, no matter how the tree is arranged. With 2 nodes, both nodes are equidistance from one another, so both are valid. With one 1 node, is it easy to see that it is as minimially distance to itself.

Complexity: O(n) time and space

import queue
import operator

class Solution:
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        init = {0:[], 1:[0], 2:[0,1]}
        if n <= 2:
            return init[n]

        g = {i:set() for i in range(0, n)}
        for s, e in edges:
            g[s].add(e)
            g[e].add(s)

        leaves = [node for node in g if len(g[node]) == 1]

        while n > 2:
            n -= len(leaves)
            next_leaves = []
            for leaf in leaves:
                link = g[leaf].pop()
                g[link].remove(leaf)
                if len(g[link]) == 1:
                    next_leaves.append(link)
            leaves = next_leaves
        return leaves