What happens if you not handling single node tree (n=1) separately?

Code may return empty list or error Fix: Add explicit check for n == 1 and return [0]

What happens if you removing leaves but not updating degrees correctly?

Infinite loop or incorrect results Fix: Decrease neighbor degrees and add new leaves only when degree becomes 1

What happens if you using bfs from each node without pruning?

Time limit exceeded on large inputs Fix: Use leaf trimming approach instead of brute force BFS from each node

What happens if you returning more than two nodes as centroids?

Incorrect output, since MHT roots are at most two Fix: Stop trimming when remaining nodes ≤ 2 and return them

Interview Preptopological-sortmediumAmazonGoogle

Minimum Height Trees (Centroid by Trimming)

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

mediumGRAPHAmazonGoogle

Imagine you want to build a communication network with the minimum possible maximum distance from a central hub to any node. Finding the best hub(s) is like finding the tree's center(s).

💡 This problem involves understanding tree structures and how to find nodes that minimize the height of the tree when chosen as roots. Beginners often struggle because it requires insight into graph properties and efficient pruning techniques rather than straightforward traversal.

📋

Problem Statement

Given an undirected graph with n nodes labeled from 0 to n-1, and a list of edges where each edge connects two nodes, find all the roots of Minimum Height Trees (MHTs). A Minimum Height Tree is a rooted tree with the minimum possible height among all possible rooted trees formed from the graph. Return a list of all such root labels.

1 ≤ n ≤ 10^5edges.length = n - 10 ≤ edges[i][0], edges[i][1] < nAll pairs (edges[i][0], edges[i][1]) are distinctThe input graph is guaranteed to be a tree (connected and acyclic)

💡

Example

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

Output[1]

Choosing node 1 as root results in a tree of height 1, which is minimal.

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

Output[3,4]

Both nodes 3 and 4 can be roots of MHTs with height 2.

n = 1, edges = [] → [0] single node tree
n = 2, edges = [[0,1]] → [0,1] both nodes are MHT roots
Star shaped tree with one center and all leaves → center node only
Line shaped tree (chain) → two middle nodes as roots if even length

⚠️

Common Mistakes

Not handling single node tree (n=1) separately

Code may return empty list or error

✅ Add explicit check for n == 1 and return [0]

Removing leaves but not updating degrees correctly

Infinite loop or incorrect results

✅ Decrease neighbor degrees and add new leaves only when degree becomes 1

Using BFS from each node without pruning

Time limit exceeded on large inputs

✅ Use leaf trimming approach instead of brute force BFS from each node

Returning more than two nodes as centroids

Incorrect output, since MHT roots are at most two

✅ Stop trimming when remaining nodes ≤ 2 and return them

🧠

Brute Force (Calculate Height for Each Node as Root)

💡 This approach exists to build intuition by directly simulating the problem definition, even though it is inefficient. It helps understand what 'minimum height' means by explicitly computing heights.

Intuition

For each node, treat it as the root and compute the height of the tree by BFS or DFS. The nodes with the smallest height are the answer.

Algorithm

For each node from 0 to n-1:
Perform BFS/DFS to find the height of the tree rooted at that node.
Track the minimum height found and the nodes that achieve it.
Return all nodes with the minimum height.

💡 The main challenge is that computing height for each root requires traversing the entire tree repeatedly, which is expensive.

</>

Code

from collections import deque

def findMinHeightTrees(n, edges):
    if n == 1:
        return [0]

    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    def bfs(root):
        visited = [False] * n
        queue = deque([(root, 0)])
        visited[root] = True
        max_depth = 0
        while queue:
            node, depth = queue.popleft()
            max_depth = max(max_depth, depth)
            for nei in graph[node]:
                if not visited[nei]:
                    visited[nei] = True
                    queue.append((nei, depth + 1))
        return max_depth

    min_height = float('inf')
    res = []
    for i in range(n):
        height = bfs(i)
        if height < min_height:
            min_height = height
            res = [i]
        elif height == min_height:
            res.append(i)
    return res

# Driver code
if __name__ == '__main__':
    print(findMinHeightTrees(4, [[1,0],[1,2],[1,3]]))  # Output: [1]

Line Notes

if n == 1:Handle trivial single-node tree quickly

graph = [[] for _ in range(n)]Build adjacency list for efficient neighbor lookup

def bfs(root):Define BFS to compute height from a given root

queue = deque([(root, 0)])Initialize queue with root node and depth 0

max_depth = max(max_depth, depth)Track maximum depth reached during BFS

for i in range(n):Try each node as root to find minimum height

height = bfs(i)Compute height for current root candidate

if height < min_height:Update minimum height and result list accordingly

import java.util.*;

public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Collections.singletonList(0);

        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        int minHeight = Integer.MAX_VALUE;
        List<Integer> res = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int height = bfs(i, graph, n);
            if (height < minHeight) {
                minHeight = height;
                res.clear();
                res.add(i);
            } else if (height == minHeight) {
                res.add(i);
            }
        }
        return res;
    }

    private int bfs(int root, List<List<Integer>> graph, int n) {
        boolean[] visited = new boolean[n];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{root, 0});
        visited[root] = true;
        int maxDepth = 0;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int node = curr[0], depth = curr[1];
            maxDepth = Math.max(maxDepth, depth);
            for (int nei : graph.get(node)) {
                if (!visited[nei]) {
                    visited[nei] = true;
                    queue.offer(new int[]{nei, depth + 1});
                }
            }
        }
        return maxDepth;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.findMinHeightTrees(4, new int[][]{{1,0},{1,2},{1,3}})); // [1]
    }
}

Line Notes

if (n == 1) return Collections.singletonList(0);Quickly handle single node tree

List<List<Integer>> graph = new ArrayList<>();Create adjacency list for graph

for (int i = 0; i < n; i++) graph.add(new ArrayList<>());Initialize adjacency lists for each node

queue.offer(new int[]{root, 0});Start BFS from root with depth 0

maxDepth = Math.max(maxDepth, depth);Keep track of max depth during BFS

for (int i = 0; i < n; i++) {Try each node as root to find minimal height

if (height < minHeight) {Update minimum height and result list

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) return {0};

        vector<vector<int>> graph(n);
        for (auto& e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }

        int minHeight = INT_MAX;
        vector<int> res;

        for (int i = 0; i < n; i++) {
            int height = bfs(i, graph, n);
            if (height < minHeight) {
                minHeight = height;
                res.clear();
                res.push_back(i);
            } else if (height == minHeight) {
                res.push_back(i);
            }
        }
        return res;
    }

private:
    int bfs(int root, vector<vector<int>>& graph, int n) {
        vector<bool> visited(n, false);
        queue<pair<int,int>> q;
        q.push({root, 0});
        visited[root] = true;
        int maxDepth = 0;

        while (!q.empty()) {
            auto [node, depth] = q.front(); q.pop();
            maxDepth = max(maxDepth, depth);
            for (int nei : graph[node]) {
                if (!visited[nei]) {
                    visited[nei] = true;
                    q.push({nei, depth + 1});
                }
            }
        }
        return maxDepth;
    }
};

// Driver code
int main() {
    Solution sol;
    vector<vector<int>> edges = {{1,0},{1,2},{1,3}};
    vector<int> res = sol.findMinHeightTrees(4, edges);
    for (int r : res) cout << r << ' '; // Output: 1
    cout << endl;
    return 0;
}

Line Notes

if (n == 1) return {0};Handle trivial single-node tree quickly

vector<vector<int>> graph(n);Build adjacency list for efficient neighbor lookup

q.push({root, 0});Initialize BFS queue with root and depth 0

maxDepth = max(maxDepth, depth);Track maximum depth reached during BFS

for (int i = 0; i < n; i++) {Try each node as root to find minimum height

int height = bfs(i, graph, n);Compute height for current root candidate

if (height < minHeight) {Update minimum height and result list accordingly

function findMinHeightTrees(n, edges) {
    if (n === 1) return [0];

    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }

    function bfs(root) {
        const visited = new Array(n).fill(false);
        const queue = [[root, 0]];
        visited[root] = true;
        let maxDepth = 0;

        while (queue.length > 0) {
            const [node, depth] = queue.shift();
            maxDepth = Math.max(maxDepth, depth);
            for (const nei of graph[node]) {
                if (!visited[nei]) {
                    visited[nei] = true;
                    queue.push([nei, depth + 1]);
                }
            }
        }
        return maxDepth;
    }

    let minHeight = Infinity;
    const res = [];
    for (let i = 0; i < n; i++) {
        const height = bfs(i);
        if (height < minHeight) {
            minHeight = height;
            res.length = 0;
            res.push(i);
        } else if (height === minHeight) {
            res.push(i);
        }
    }
    return res;
}

// Driver code
console.log(findMinHeightTrees(4, [[1,0],[1,2],[1,3]])); // Output: [1]

Line Notes

if (n === 1) return [0];Handle single node tree quickly

const graph = Array.from({length: n}, () => []);Build adjacency list for graph

const queue = [[root, 0]];Initialize BFS queue with root and depth 0

maxDepth = Math.max(maxDepth, depth);Track maximum depth during BFS

for (let i = 0; i < n; i++) {Try each node as root to find minimal height

const height = bfs(i);Compute height for current root candidate

if (height < minHeight) {Update minimum height and result list

⏱

Complexity

TimeO(n^2) because for each node we do a BFS/DFS that takes O(n) time

SpaceO(n) for adjacency list and BFS queue

We run BFS from each node, each BFS takes O(n), repeated n times leads to O(n^2).

💡 For n=20, this means roughly 400 BFS traversals, which is manageable but grows quickly and becomes impractical for large n.

Interview Verdict: TLE for large inputs

This approach is too slow for large trees but is useful to understand the problem and correctness before optimizing.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n^2)`	`O(n)`	No	N/A	Mention only - never code due to inefficiency
2. Better (Leaf Trimming BFS)	`O(n)`	`O(n)`	No	N/A	Code this approach for optimal solution
3. Optimal (Leaf Trimming with Early Exit)	`O(n)`	`O(n)`	No	N/A	Code this for clean and robust solution

Practice

(1/5)

1. Given the following Python code snippet implementing the optimal alien dictionary solution, what is the final returned order for the input words = ["wrt", "wrf", "er", "ett", "rftt"]?

from collections import defaultdict, deque

def alienOrder(words):
    graph = defaultdict(set)
    in_degree = {c: 0 for word in words for c in word}

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        min_len = min(len(w1), len(w2))
        if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
            return ""
        for j in range(min_len):
            if w1[j] != w2[j]:
                if w2[j] not in graph[w1[j]]:
                    graph[w1[j]].add(w2[j])
                    in_degree[w2[j]] += 1
                break

    queue = deque([c for c in in_degree if in_degree[c] == 0])
    order = []
    while queue:
        c = queue.popleft()
        order.append(c)
        for nei in graph[c]:
            in_degree[nei] -= 1
            if in_degree[nei] == 0:
                queue.append(nei)
    if len(order) < len(in_degree):
        return ""
    return "".join(order)

print(alienOrder(words))

easy

A. "wretf"

B. "wertf"

C. "wert"

D. "wrtef"

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Build graph and in-degree map

Step 2: Perform BFS topological sort

Final Answer:

Quick Check:

Solution

Step 1: Identify operations on vertices and edges

Step 2: Sum total work

Final Answer:

Quick Check:

Solution

Step 1: Understand variant requirement

Step 2: Confirm correct approach

Step 3: Reject incorrect modifications

Final Answer:

Quick Check:

Solution

Step 1: Understand repeated courses and prerequisites

Step 2: Analyze BFS topological sort applicability

Final Answer:

Quick Check:

Solution

Step 1: Understand impact of repeated elements

Step 2: Adjust graph and DFS accordingly

Final Answer:

Quick Check:

Ready to prove it?