Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using topological sort strategy.
A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.
Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).
Return a list of all MHTs' root labels. You can return the answer in any order.
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
Example 1:
Input: n = 4, edges = [[1,0],[1,2],[1,3]] Output: [1] Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.
Example 2:
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] Output: [3,4]
Constraints:
1 <= n <= 2 * 104edges.length == n - 10 <= ai, bi < nai != bi(ai, bi) are distinct.Problem summary: A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree. Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs). Return a list of all MHTs' root labels. You can return the answer in any order. The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Topological Sort
4 [[1,0],[1,2],[1,3]]
6 [[3,0],[3,1],[3,2],[3,4],[5,4]]
course-schedule)course-schedule-ii)collect-coins-in-a-tree)count-pairs-of-connectable-servers-in-a-weighted-tree-network)find-minimum-diameter-after-merging-two-trees)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #310: Minimum Height Trees
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) {
return List.of(0);
}
List<Integer>[] g = new List[n];
Arrays.setAll(g, k -> new ArrayList<>());
int[] degree = new int[n];
for (int[] e : edges) {
int a = e[0], b = e[1];
g[a].add(b);
g[b].add(a);
++degree[a];
++degree[b];
}
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
if (degree[i] == 1) {
q.offer(i);
}
}
List<Integer> ans = new ArrayList<>();
while (!q.isEmpty()) {
ans.clear();
for (int i = q.size(); i > 0; --i) {
int a = q.poll();
ans.add(a);
for (int b : g[a]) {
if (--degree[b] == 1) {
q.offer(b);
}
}
}
}
return ans;
}
}
// Accepted solution for LeetCode #310: Minimum Height Trees
func findMinHeightTrees(n int, edges [][]int) (ans []int) {
if n == 1 {
return []int{0}
}
g := make([][]int, n)
degree := make([]int, n)
for _, e := range edges {
a, b := e[0], e[1]
g[a] = append(g[a], b)
g[b] = append(g[b], a)
degree[a]++
degree[b]++
}
q := []int{}
for i, d := range degree {
if d == 1 {
q = append(q, i)
}
}
for len(q) > 0 {
ans = []int{}
for i := len(q); i > 0; i-- {
a := q[0]
q = q[1:]
ans = append(ans, a)
for _, b := range g[a] {
degree[b]--
if degree[b] == 1 {
q = append(q, b)
}
}
}
}
return
}
# Accepted solution for LeetCode #310: Minimum Height Trees
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n == 1:
return [0]
g = [[] for _ in range(n)]
degree = [0] * n
for a, b in edges:
g[a].append(b)
g[b].append(a)
degree[a] += 1
degree[b] += 1
q = deque(i for i in range(n) if degree[i] == 1)
ans = []
while q:
ans.clear()
for _ in range(len(q)):
a = q.popleft()
ans.append(a)
for b in g[a]:
degree[b] -= 1
if degree[b] == 1:
q.append(b)
return ans
// Accepted solution for LeetCode #310: Minimum Height Trees
struct Solution;
use std::collections::VecDeque;
impl Solution {
fn find_min_height_trees(n: i32, edges: Vec<Vec<i32>>) -> Vec<i32> {
let n = n as usize;
if n == 1 {
return vec![0];
}
let mut graph: Vec<Vec<usize>> = vec![vec![]; n];
let mut visited: Vec<bool> = vec![false; n];
let mut degree: Vec<usize> = vec![0; n];
for e in edges {
let u = e[0] as usize;
let v = e[1] as usize;
graph[u].push(v);
graph[v].push(u);
degree[u] += 1;
degree[v] += 1;
}
let mut leaves: VecDeque<usize> = VecDeque::new();
for i in 0..n {
if graph[i].len() == 1 {
leaves.push_back(i);
}
}
let mut m = n;
while m > 2 {
m -= leaves.len();
for _ in 0..leaves.len() {
let u = leaves.pop_front().unwrap();
visited[u] = true;
for &v in &graph[u] {
if !visited[v] {
degree[v] -= 1;
if degree[v] == 1 {
leaves.push_back(v);
}
}
}
}
}
leaves.into_iter().map(|x| x as i32).collect()
}
}
#[test]
fn test() {
let n = 4;
let edges = vec_vec_i32![[1, 0], [1, 2], [1, 3]];
let mut res = vec![1];
let mut ans = Solution::find_min_height_trees(n, edges);
ans.sort_unstable();
res.sort_unstable();
assert_eq!(ans, res);
let n = 6;
let edges = vec_vec_i32![[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]];
let mut res = vec![3, 4];
let mut ans = Solution::find_min_height_trees(n, edges);
ans.sort_unstable();
res.sort_unstable();
assert_eq!(ans, res);
let n = 3;
let edges = vec_vec_i32![[0, 1], [0, 2]];
let mut res = vec![0];
let mut ans = Solution::find_min_height_trees(n, edges);
ans.sort_unstable();
res.sort_unstable();
assert_eq!(ans, res);
}
// Accepted solution for LeetCode #310: Minimum Height Trees
function findMinHeightTrees(n: number, edges: number[][]): number[] {
if (n === 1) {
return [0];
}
const g: number[][] = Array.from({ length: n }, () => []);
const degree: number[] = Array(n).fill(0);
for (const [a, b] of edges) {
g[a].push(b);
g[b].push(a);
++degree[a];
++degree[b];
}
const q: number[] = [];
for (let i = 0; i < n; ++i) {
if (degree[i] === 1) {
q.push(i);
}
}
const ans: number[] = [];
while (q.length > 0) {
ans.length = 0;
const t: number[] = [];
for (const a of q) {
ans.push(a);
for (const b of g[a]) {
if (--degree[b] === 1) {
t.push(b);
}
}
}
q.splice(0, q.length, ...t);
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Repeatedly find a vertex with no incoming edges, remove it and its outgoing edges, and repeat. Finding the zero-in-degree vertex scans all V vertices, and we do this V times. Removing edges touches E edges total. Without an in-degree array, this gives O(V × E).
Build an adjacency list (O(V + E)), then either do Kahn's BFS (process each vertex once + each edge once) or DFS (visit each vertex once + each edge once). Both are O(V + E). Space includes the adjacency list (O(V + E)) plus the in-degree array or visited set (O(V)).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.