DSA problem
Minimum Height Trees
A tree is an undirected connected graph with n nodes labeled 0 to n - 1 and exactly n - 1 edges. For any node chosen as root, the tree has a height equal to the maximum number of edges between the root and any leaf. Among all possible roots, the trees with the minimum height are called minimum height trees (MHTs). Given the edges of such a tree, return all the labels that can serve as roots of an MHT.
A brute-force approach would BFS from every node to compute its eccentricity and pick the minima, costing O(n^2). The clever observation that yields a linear algorithm is that the roots of all MHTs are exactly the centroids of the tree, of which there are always 1 or 2. The centroid sits in the middle of the longest path (the diameter), so the optimum height is ⌈diameter / 2⌉.
We compute the centroids with a topological-sort style peeling: treat each leaf (degree 1 in the undirected sense) as a Kahn source, then repeatedly strip off the current layer of leaves. After each layer is removed, the remaining graph is still a tree with fewer leaves; the new leaves form the next layer. This is exactly Kahn's algorithm applied to an undirected tree using the in/out symmetric "degree" of each node.
We stop when at most 2 nodes remain — those are the centroids and hence the labels we return. Because every node and edge is touched a constant number of times during the peeling, the total cost is O(n) time and O(n) space, which is asymptotically optimal.
Examples
n = 4, edges = [[1,0],[1,2],[1,3]][1]n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]][3,4]n = 1, edges = [][0]Constraints
- 1 <= n <= 2 * 10^4
- edges.length == n - 1
- 0 <= a, b < n
- a != b
- All the pairs (a, b) are distinct.
- The given input is guaranteed to be a tree and there will be no repeated edges.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.