Minimum Height Trees

Try to solve the Minimum Height Trees problem.

We'll cover the following

Statement#

You are given nn as the number of nodes and a 2D array of edges representing a tree having the following properties:

  • It is an acyclic, undirected graph containing nn nodes and n−1n-1 edges.

  • The nodes are labeled from 00 to n−1n-1.

  • An edge at the ithi^{th} index is represented as [ai,bi][a_i, b_i], which denotes that there is an undirected edge connecting the nodes aia_i and bib_i.

Your task is to find all possible root nodes that can be used to create trees of minimum height. The height of a tree is the length of the longest path from the root node to any leaf node.

Note: The order of root nodes in the result does not matter.

Constraints

  • 1≤n≤5001 \leq n \leq 500
  • edges.length ==n−1== n - 1
  • ai≠bia_i \neq b_i
  • Each edge is unique.

Examples#

canvasAnimation-image

1 of 3

canvasAnimation-image

2 of 3

canvasAnimation-image

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Minimum Height Trees

1

What is the output if the following number of nodes and edges are given as input?

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

A)

[0]

B)

[1]

C)

[0, 1]

D)

[1, 3]

Question 1 of 30 attempted

Try it yourself#

Implement your solution in the following coding playground.

An optimal solution to this problem runs in O(n) time and takes O(n) space.

Python
usercode > main.py
Input #1
Input #2
Minimum Height Trees

Solution: Diameter of Binary Tree

Solution: Minimum Height Trees