Minimum Height Trees
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]
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;}