class Solution(object):
def findMinHeightTrees(self, n, edges):
graph = [[] for i in range(n)]
for v1, v2 in edges:
graph[v1].append(v2)
graph[v2].append(v1)
p1 = self.FindLongestPath(graph, 0)
p2 = self.FindLongestPath(graph, p1[1])
if len(p2) % 2: return [p2[len(p2)/2]]
else: return [p2[len(p2)/2  1], p2[len(p2)/2]]
def FindLongestPath(self, graph, root):
queue = collections.deque([[root]])
traversed = set([root])
while queue:
path = queue.pop()
for v in graph[path[1]]:
if v not in traversed:
queue.appendleft(path + [v])
traversed.add(v)
return path
Compact Python solution using two BFS


queue.appendleft(path + [v])
This way of keeping track of paths can cost you O(n^2) space. If you have an O(N) number of branches later on you'll be keeping track of O(N) paths with each of them taking up O(N) space. Consider a tree that keeps breaking out into multiple branches.