mediumGraphsPure DSA~30 min
Choose Roots That Minimize Tree Height
A team's reporting structure is an undirected tree. Pick the person (or two people) to root the org chart at so that the deepest chain of reports is as short as possible.
Problem
Given a tree with n nodes (0..n-1) described by n-1 undirected edges, a minimum-height tree (MHT) is one rooted at a node that minimizes the tree's height. Return the list of all root labels that achieve the minimum height (there are at most two).
Input
An integer n and an edge list edges of n-1 undirected pairs.
Output
A list of all roots yielding minimum height (order does not matter).
Constraints
- 1 <= n <= 2*10^4
- edges.length == n - 1
- The input is guaranteed to form a valid tree.
Examples
Example 1
Input
n = 4, edges = [[1,0],[1,2],[1,3]]
Output
[1]
Rooting at the center node 1 gives height 1.
Example 2
Input
n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output
[3,4]
The two central nodes both yield the minimum height.