Minimum Height Trees
A tree is an undirected graph in which any two vertices are connected by exactly one path. Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges, you can choose any node of the tree as the root. The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf. Return a list of all MHTs root labels. You can return the answer in any order.

30:00

Minimum Height Trees
medium
Topics
Companies

A tree is an undirected graph in which any two vertices are connected by exactly one path. Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges, you can choose any node of the tree as the root. The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf. Return a list of all MHTs root labels. You can return the answer in any order.

Example 1:
Input: {"n":4,"edges":[[1,0],[1,2],[1,3]]}
Output: [1]
Constraints:

  • 1≤n≤2×1041 \leq n \leq 2 \times 10^4

  • edges.length==n−1\text{edges.length} == n - 1

  • 0≤ai,bi<n0 \leq a_i, b_i < n

  • ai≠bia_i \neq b_i

  • All pairs (ai,bi)(a_i, b_i) are distinct.

  • The given input is guaranteed to be a tree.

Input
arr ={"n":4,"edges":[[1,0],[1,2],[1,3]]}

Built graph with 4 nodes and 3 edges

Remaining nodes: 4

Nodes and Degrees

0

deg:1

1

deg:3

2

deg:1

3

deg:1
Leaf
MHT Root
Removed
Variables
No variables to display
DepthFunction Call
Stack empty
0/3