 All Problems
Minimum Height Trees
medium
topological sort
graph
tree
google
amazon

A tree is an undirected graph with no cycles. Given a tree with n nodes (labeled 0 to n-1) and its edges, find all nodes that can be roots of minimum height trees (MHTs).

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= n <= 2 * 10^4
  • edges.length == n - 1
Run to check your code against the sample cases, or submit to run every case