Minimum Height Trees (Centroid by Trimming)

📋

Problem

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).

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)

Edge cases: n = 1, edges = [] → [0] single node treen = 2, edges = [[0,1]] → [0,1] both nodes are MHT rootsStar shaped tree with one center and all leaves → center node only

</>

IDE

def findMinHeightTrees(n: int, edges: list[list[int]]) -> list[int]:public List<Integer> findMinHeightTrees(int n, int[][] edges)vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges)function findMinHeightTrees(n, edges)

def findMinHeightTrees(n, edges):
    # Write your solution here
    pass

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
    // Write your solution here
    return {};
}

function findMinHeightTrees(n, edges) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [0]Stopping leaf trimming too early, returning only one node when two centroids exist.✅ Change loop condition to continue trimming until number of remaining nodes <= 2.

Wrong: [0,2]Incorrect leaf trimming logic removing wrong nodes or not updating degrees properly.✅ Ensure degrees are updated after removing leaves and only nodes with degree 1 are removed each iteration.

Wrong: [1]Greedy approach picking single centroid without full trimming in trees with two centroids.✅ Implement iterative leaf trimming until <= 2 nodes remain instead of greedy pick.

Wrong: TLEBrute force BFS from each node causing O(n^2) time complexity.✅ Use leaf trimming approach with degree array and queue for O(n) complexity.

✓

Test Cases

Focus on handling smallest and boundary inputs correctly.

Test your trimming logic on chains and branching trees carefully.

Optimize your solution to linear time using leaf trimming with a queue.

t1_01basic

Input{"n":4,"edges":[[1,0],[1,2],[1,3]]}

Expected[1]

⏱ Performance - must finish in 2000ms

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

💡 Consider trimming leaves layer by layer until 1 or 2 nodes remain.

💡 Use a queue to remove all leaves (degree 1 nodes) iteratively.

💡 The remaining nodes after trimming are the MHT roots.

Why it failed: Incorrect output means leaf trimming logic is wrong; ensure you remove all leaves simultaneously and update degrees correctly.

✓ Correctly identifies the centroid node as the MHT root.

t1_02basic

Input{"n":6,"edges":[[0,3],[1,3],[2,3],[4,3],[5,4]]}

Expected[3,4]

⏱ Performance - must finish in 2000ms

The tree is like a star with an extra leaf on node 4; trimming leaves leads to nodes 3 and 4 as centroids.

💡 After removing leaves, check which nodes remain as potential roots.

💡 Nodes with degree > 1 after trimming are candidates for MHT roots.

💡 The last one or two nodes remaining after leaf trimming are the answer.

Why it failed: If output misses one centroid, likely leaf trimming stops too early or updates degrees incorrectly.

✓ Correctly finds both centroids in a tree with two MHT roots.

t2_01edge

Input{"n":1,"edges":[]}

Expected[0]

⏱ Performance - must finish in 2000ms

Single node tree; the only node is the MHT root.

💡 Check if n=1 and return [0] immediately.

💡 No edges means no trimming needed.

💡 Handle this base case separately to avoid errors.

Why it failed: Failing this means code does not handle single node base case; add explicit check for n=1.

✓ Correctly returns the single node as MHT root.

t2_02edge

Input{"n":2,"edges":[[0,1]]}

Expected[0,1]

⏱ Performance - must finish in 2000ms

Two nodes connected; both are centroids and MHT roots.

💡 When only two nodes, both are roots of MHT.

💡 Leaf trimming removes leaves until 1 or 2 nodes remain.

💡 Ensure your code returns both nodes when two remain.

Why it failed: If only one node returned, leaf trimming stops too early or does not handle two-node case properly.

✓ Correctly returns both nodes as MHT roots.

t2_03edge

Input{"n":4,"edges":[[0,1],[1,2],[2,3]]}

Expected[1,2]

⏱ Performance - must finish in 2000ms

Line shaped tree with even length; two middle nodes are MHT roots.

💡 In chains with even length, two centroids exist.

💡 Leaf trimming removes ends until two nodes remain.

💡 Verify your trimming loop continues until <= 2 nodes remain.

Why it failed: If only one node returned, trimming loop condition is incorrect; fix to continue until <= 2 nodes remain.

✓ Correctly identifies two centroids in chain.

t3_01corner

Input{"n":5,"edges":[[0,1],[1,2],[2,3],[3,4]]}

Expected[2]

⏱ Performance - must finish in 2000ms

Line shaped tree with odd length; single middle node is centroid.

💡 Check how leaf trimming handles odd length chains.

💡 Only one node should remain after trimming leaves.

💡 Ensure trimming loop stops when nodes count <= 2.

Why it failed: If two nodes returned, trimming loop condition is off by one; fix loop to stop at <= 2 nodes.

✓ Correctly returns single centroid for odd length chain.

t3_02corner

Input{"n":7,"edges":[[0,1],[1,2],[1,3],[3,4],[4,5],[4,6]]}

Expected[1,4]

⏱ Performance - must finish in 2000ms

Tree with two centroids due to branching; leaf trimming finds both.

💡 Greedy approach picking only one centroid fails here.

💡 Leaf trimming must continue until <= 2 nodes remain.

💡 Check degree updates carefully after each trimming.

Why it failed: If only one centroid returned, code uses greedy pick instead of full trimming; fix to iterative leaf trimming.

✓ Correctly identifies both centroids in branching tree.

t3_03corner

Input{"n":3,"edges":[[0,1],[1,2]]}

Expected[1]

⏱ Performance - must finish in 2000ms

Small chain; middle node is centroid.

💡 Check that leaf trimming handles small chains correctly.

💡 Do not stop trimming too early.

💡 Ensure degrees are updated after each leaf removal.

Why it failed: If output is [0,2], leaf trimming logic is reversed; fix to remove leaves properly and update degrees.

✓ Correctly returns middle node as centroid.

t4_01performance

Input{"n":100,"edges":[[0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,8],[8,9],[9,10],[10,11],[11,12],[12,13],[13,14],[14,15],[15,16],[16,17],[17,18],[18,19],[19,20],[20,21],[21,22],[22,23],[23,24],[24,25],[25,26],[26,27],[27,28],[28,29],[29,30],[30,31],[31,32],[32,33],[33,34],[34,35],[35,36],[36,37],[37,38],[38,39],[39,40],[40,41],[41,42],[42,43],[43,44],[44,45],[45,46],[46,47],[47,48],[48,49],[49,50],[50,51],[51,52],[52,53],[53,54],[54,55],[55,56],[56,57],[57,58],[58,59],[59,60],[60,61],[61,62],[62,63],[63,64],[64,65],[65,66],[66,67],[67,68],[68,69],[69,70],[70,71],[71,72],[72,73],[73,74],[74,75],[75,76],[76,77],[77,78],[78,79],[79,80],[80,81],[81,82],[82,83],[83,84],[84,85],[85,86],[86,87],[87,88],[88,89],[89,90],[90,91],[91,92],[92,93],[93,94],[94,95],[95,96],[96,97],[97,98],[98,99]]}

Expectednull

⏱ Performance - must finish in 2000ms

Chain of 100 nodes; O(n) leaf trimming must complete within 2 seconds.

💡 Use O(n) leaf trimming approach, not O(n^2) brute force.

💡 Avoid recomputing heights for each node.

💡 Process each node and edge at most once.

Why it failed: TLE indicates brute force BFS from each node; fix to use iterative leaf trimming with degree array and queue.

✓ Efficient O(n) leaf trimming approach confirmed.

Practice

1. Consider the following Python code implementing the optimal approach to find eventual safe states. Given the input graph = [[1],[2],[3],[]], what is the final returned list of safe nodes?

from collections import deque

def eventualSafeNodes(graph):
    n = len(graph)
    reverse_graph = [[] for _ in range(n)]
    in_degree = [0] * n

    for u in range(n):
        for v in graph[u]:
            reverse_graph[v].append(u)
        in_degree[u] = len(graph[u])

    queue = deque([i for i in range(n) if in_degree[i] == 0])
    safe = []

    while queue:
        node = queue.popleft()
        safe.append(node)
        for prev in reverse_graph[node]:
            in_degree[prev] -= 1
            if in_degree[prev] == 0:
                queue.append(prev)

    return sorted(safe)

easy

A. [3]

B. [0, 3]

C. [0, 1, 2, 3]

D. [1, 2, 3]

Solution

1. Step 1: Initialize in-degree and reverse graph

   Graph has edges: 0->1, 1->2, 2->3, 3->none. So in_degree = [1,1,1,0], reverse_graph = [[],[0],[1],[2]].

2. Step 2: Process queue starting with nodes having in-degree 0

   Start with node 3 in queue. Pop 3, safe=[3]. Decrement in_degree of 2 to 0, add 2 to queue. Pop 2, safe=[3,2]. Decrement in_degree of 1 to 0, add 1. Pop 1, safe=[3,2,1]. Decrement in_degree of 0 to 0, add 0. Pop 0, safe=[3,2,1,0].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   All nodes lead to terminal node 3, so all are safe [OK]

Hint: Nodes with zero out-degree start the safe node chain [OK]

Common Mistakes:

• Forgetting to sort final safe list
• Miscounting in-degree initialization
• Off-by-one errors in queue processing

2. You are given n courses labeled from 1 to n and a list of prerequisite pairs where each pair [a, b] means you must take course a before course b. You want to find the minimum number of semesters needed to complete all courses if you can take any number of courses in parallel as long as their prerequisites are met. Which algorithmic approach guarantees finding the minimum semesters efficiently?

easy

A. Use dynamic programming to try all subsets of courses and pick the minimal semester count.

B. Use a greedy approach that always picks the course with the fewest prerequisites next.

C. Use a topological sort with BFS (Kahn's Algorithm) to process courses level by level based on in-degree zero nodes.

D. Use depth-first search (DFS) to detect cycles and then schedule courses in reverse postorder.

Solution

1. Step 1: Understand the problem constraints

   The problem requires scheduling courses respecting prerequisites and minimizing semesters, allowing parallel courses per semester.

2. Step 2: Identify the suitable algorithm

   Kahn's Algorithm (topological sort with BFS) processes nodes with zero in-degree in batches (levels), naturally modeling semesters and ensuring minimal semesters.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Level-by-level BFS matches semesters needed [OK]

Hint: Minimum semesters = levels in topological BFS [OK]

Common Mistakes:

• Thinking greedy picking minimal prerequisites works
• Confusing DFS order with minimal semester scheduling
• Trying exponential DP without pruning

3. You are given a list of sequences, each representing partial orderings of elements. Your task is to determine if there exists exactly one sequence that can be constructed which is consistent with all these partial orderings and matches a given original sequence. Which algorithmic approach best guarantees an efficient and correct solution for this problem?

easy

A. Use brute force to generate all permutations of the original sequence and check which ones are supersequences of all given sequences.

B. Apply a greedy approach by always choosing the smallest available element not yet placed, hoping to build the unique sequence.

C. Use dynamic programming to count the number of ways to interleave the sequences and verify if only one matches the original.

D. Construct a directed graph from the sequences and perform a DFS postorder topological sort with cycle detection and uniqueness verification.

Solution

1. Step 1: Understand problem constraints

   The problem requires verifying if exactly one sequence matches all partial orderings, which is a classic unique topological order problem.

2. Step 2: Identify suitable algorithm

   Brute force is inefficient; greedy and DP approaches do not guarantee correctness or uniqueness checks. DFS postorder topological sort with cycle detection and uniqueness verification efficiently solves the problem.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DFS topological sort with uniqueness check is standard for unique sequence reconstruction [OK]

Hint: Unique topo order requires graph + DFS with uniqueness check [OK]

Common Mistakes:

• Assuming greedy or DP can guarantee uniqueness
• Trying brute force despite factorial complexity

4. What is the time complexity of the optimal approach that uses the reversed graph and Kahn's algorithm to find eventual safe states in a graph with V vertices and E edges?

medium

A. O(V + E) because each edge and vertex is processed once during graph reversal and BFS

B. O(V^2) because we process each node and its neighbors repeatedly

C. O(V * E) due to nested loops over vertices and edges

D. O(E log V) because of sorting the safe nodes at the end

Solution

1. Step 1: Analyze graph reversal and in-degree computation

   Reversing the graph and computing in-degree requires iterating over all edges once, O(E).

2. Step 2: Analyze BFS processing

   Each node is enqueued and dequeued at most once, and each edge is considered once when decrementing in-degree, total O(V + E).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time in vertices and edges matches BFS and graph reversal [OK]

Hint: Each edge and vertex processed once in BFS + reversal [OK]

Common Mistakes:

• Assuming nested loops cause O(V*E)
• Confusing sorting cost as dominant
• Forgetting BFS processes each edge once

5. If the problem is extended so that the same element can appear multiple times in the matrix (i.e., reuse allowed), which modification to the topological sort approach is necessary to correctly build the matrix?

hard

A. No change needed; reuse does not affect topological ordering

B. Replace topological sort with a longest path algorithm to handle repeated elements

C. Track counts of each element and assign positions based on frequency, not just order

D. Modify graph to allow self-loops and update cycle detection accordingly

Solution

1. Step 1: Understand reuse impact on matrix construction

   Allowing reuse means elements can appear multiple times, so positions must reflect frequency, not just order.

2. Step 2: Adjust algorithm to track counts and assign positions accordingly

   Topological order alone does not handle multiple occurrences; tracking counts and assigning positions based on frequency is necessary.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Frequency tracking ensures correct placement of repeated elements [OK]

Hint: Reuse implies tracking element counts and positions [OK]

Common Mistakes:

• Assuming reuse needs no algorithm change
• Ignoring frequency of elements
• Replacing topological sort unnecessarily