Minimum Height Trees

Medium

Problem

A tree has n nodes and n − 1 edges. Rooting it at different nodes gives different heights. Return every node that gives the minimum height.

Example 1

Input:  n = 4, edges = [[1,0], [1,2], [1,3]]
Output: [1]

Example 2

Input:  n = 6, edges = [[3,0], [3,1], [3,2], [3,4], [5,4]]
Output: [3, 4]

Test cases

Case 1

Input:    4, [[1,0],[1,2],[1,3]]
Expected (any order): [1]

Case 2

Input:    6, [[3,0],[3,1],[3,2],[3,4],[5,4]]
Expected (any order): [3,4]

Case 3

Input:    1, []
Expected (any order): [0]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Peel leaves layer by layer

Time O(n)Space O(n)

Topological-sort style on an undirected tree: repeatedly remove all leaves (degree 1). The last one or two nodes are the centres.

function findMinHeightTrees(n, edges) {
if (n === 1) return [0];
const adj = Array.from({ length: n }, () => []);
const deg = new Array(n).fill(0);
for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); deg[a]++; deg[b]++; }
let leaves = [];
for (let i = 0; i < n; i++) if (deg[i] === 1) leaves.push(i);
let left = n;
while (left > 2) {
left -= leaves.length;
const next = [];
for (const u of leaves) for (const v of adj[u]) if (--deg[v] === 1) next.push(v);
leaves = next;
}
return leaves;
}