Minimum Height Trees
Medium · Graphs · Depth-First Search · Breadth-First Search · Graph · Topological Sort
Problem
A tree is an undirected, connected graph with no cycles. You are given n nodes labelled 0 to n - 1 and n - 1 edges, where edges[i] = [a, b] joins a and b.
Choosing a node as the root gives the tree a height: the number of edges on the longest path from the root down to a leaf. The roots with the smallest possible height give *minimum height trees*.
Return the labels of all roots that give a minimum height tree, in any order.
Peeling the leaves off layer by layer (a topological sort driven by degrees) leaves one or two centre nodes, and those are the answer.
Examples
Input: n = 5, edges = [[0,1],[1,2],[2,3],[2,4]] Output: [1,2]
Rooting at 1 or at 2 gives height 2; rooting anywhere else gives height 3. The longest path 0-1-2-3 has an odd number of edges, so it has two middle nodes.
Input: n = 4, edges = [[0,3],[1,3],[2,3]] Output: [3]
Node 3 touches every other node, so rooting there gives height 1.
Input: n = 1, edges = [] Output: [0]
With no edges, the only node is the root of a tree of height 0.
Constraints
- 1 <= n <= 2 · 10^4
- len(edges) == n - 1
- 0 <= a, b < n and a != b
- all edges are different
- the edges form a tree
Approaches
- BFS from every node — time O(n²), space O(n)
Follow-up
The answer is the middle of the tree's longest path (its diameter). Can you find it with two BFS passes instead: farthest node from anywhere, then farthest from that, then walk back half the path?
Related problems
Start free on Cariara · Coding problems · System design studio
