310. Minimum Height Trees

Problem Statement

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.

You are given a tree of n nodes labelled from 0 to n - 1. The tree is represented as an array edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the tree.

Return the labels of all nodes that are the roots of minimum height trees (MHTs). You can return the answer in any order.

A minimum height tree is a tree rooted at a node such that the tree has the smallest possible height among all possible rooted trees.

Examples

Example 1:

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree when rooted at node 1 is 1, which is the minimum possible.

Example 2:

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

Constraints

1 <= n <= 2 * 10^4
edges.length == n - 1
0 <= ai, bi < n
ai != bi
All the pairs (ai, bi) are distinct.
The given input is guaranteed to be a tree and there will be no repeated edges.

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

Tree structure: Is the graph guaranteed to be a tree? (Assumption: Yes - per constraints, input is guaranteed to be a tree with n-1 edges)
Height definition: How is tree height defined? (Assumption: Height is the number of edges in the longest path from root to any leaf)
Root selection: Can we choose any node as root? (Assumption: Yes - we want to find which node(s) as root give minimum height)
Multiple centers: Can there be multiple minimum height trees? (Assumption: Yes - there can be 1 or 2 center nodes that give minimum height)
Return format: Should we return all possible roots or just one? (Assumption: Return all nodes that can serve as root for minimum height trees)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

For each node, calculate the height of the tree when that node is the root (using BFS or DFS). Return the node(s) with minimum height. This approach requires O(n) time per node to calculate height, giving O(n²) overall complexity, which is too slow for large trees.

Step 2: Semi-Optimized Approach (7 minutes)

Use the fact that minimum height trees have roots at the “center” of the tree. Find the diameter of the tree (longest path), and the center nodes of the diameter are the roots. However, finding the diameter requires two BFS passes, and identifying center nodes requires additional processing. This approach works but can be complex to implement correctly.

Step 3: Optimized Solution (8 minutes)

Use topological sort (leaf removal): repeatedly remove leaf nodes (nodes with degree 1) until 1 or 2 nodes remain. These remaining nodes are the roots of minimum height trees. The key insight is that leaves contribute to tree height, so removing them iteratively reveals the center. This achieves O(n) time complexity. Alternatively, use two BFS passes to find diameter endpoints, then find the center of the diameter. The topological approach is simpler and more intuitive: keep removing leaves until the “core” remains, which naturally identifies the optimal roots.

Solution Approach

This problem requires finding the center(s) of a tree. The key insight is that minimum height trees have their roots at the center(s) of the longest path (diameter) in the tree.

Key Insights:

Tree Centers: A tree has at most 2 centers (nodes at the middle of the longest path)
Peeling Leaves: Repeatedly remove leaves (nodes with degree 1) until 1 or 2 nodes remain
Topological Sort: Similar to Kahn’s algorithm, process nodes with indegree 1
Remaining Nodes: The 1 or 2 nodes remaining after peeling are the centers (MHT roots)

Algorithm:

Build Graph: Create adjacency list and calculate degrees
Find Leaves: Initialize queue with all nodes having degree 1
Peel Leaves Iteratively:
- Process all leaves at current level
- Remove leaves and update degrees of neighbors
- Add new leaves (degree becomes 1) to queue
- Continue until ≤ 2 nodes remain
Return Centers: Remaining nodes are the MHT roots

Solution

Solution: Peeling Leaves (Topological Sort)

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        // Essentially it is to find the path with max length, return its central node(s)
        vector<int> rtn;
        if(n == 0) return rtn;
        if(n == 1) return {0};

        // Build the adj list
        vector<vector<int>> adj(n);
        vector<int> inDegree(n, 0);

        for(auto& edge: edges) {
            int u = edge[0], v = edge[1];
            adj[u].emplace_back(v);
            adj[v].emplace_back(u);
            inDegree[u]++;
            inDegree[v]++;
        }

        // Init leaves
        queue<int> leaves;
        for(int i = 0; i < n; i++) {
            if(inDegree[i] == 1) {
                leaves.push(i);
            }
        }

        // Trim leaves until <= 2 nodes remain
        int remainingNodes = n;
        while (remainingNodes > 2) {
            int leavesSize = leaves.size();
            remainingNodes -= leavesSize;
            for(int i = 0; i < leavesSize; i++) {
                int leaf = leaves.front();
                leaves.pop();
                // The leaf has only one neighbor
                for(int neighbor: adj[leaf]) {
                    inDegree[neighbor]--;
                    if(inDegree[neighbor] == 1) {
                        leaves.push(neighbor);
                    }
                }
            }
        }
        
        // Remaining nodes are roots of MHTs
        while(!leaves.empty()) {
            rtn.emplace_back(leaves.front());
            leaves.pop();
        }
        return rtn;
    }
};

Algorithm Explanation:

Edge Cases (Lines 5-7):
- If n == 0, return empty
- If n == 1, return [0] (single node is the center)
Build Graph (Lines 9-19):
- Create adjacency list adj for undirected graph
- Calculate inDegree (degree) for each node
- For each edge [u, v], add both directions and increment degrees
Initialize Leaves (Lines 21-26):
- Find all nodes with degree == 1 (leaves)
- Add them to queue for processing
Peel Leaves Iteratively (Lines 28-42):
- While remainingNodes > 2:
  - Process all leaves at current level (batch processing)
  - For each leaf:
    - Remove it (decrement remainingNodes)
    - For each neighbor:
      - Decrement neighbor’s degree
      - If neighbor’s degree becomes 1, add to queue (new leaf)
- Continue until ≤ 2 nodes remain
Return Centers (Lines 44-48):
- Remaining nodes in queue are the centers (MHT roots)
- Return them as result

Why This Works:

Tree Centers: The center(s) of a tree are at the middle of the longest path
Peeling Leaves: Removing leaves doesn’t change the center(s) of the tree
Convergence: After peeling, 1 or 2 nodes remain (the centers)
MHT Roots: Centers minimize the maximum distance to any leaf

Example Walkthrough:

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

Tree structure:
    0
    |
    3
   /|\
  1 2 4
        \
         5

Step 1: Build Graph
  adj[0] = [3]
  adj[1] = [3]
  adj[2] = [3]
  adj[3] = [0,1,2,4]
  adj[4] = [3,5]
  adj[5] = [4]

  inDegree = [1, 1, 1, 4, 2, 1]

Step 2: Initialize Leaves
  Leaves: [0, 1, 2, 5] (degree = 1)

Step 3: First Iteration (remainingNodes = 6 > 2)
  Process leaves: [0, 1, 2, 5]
  
  Process 0:
    Neighbor: 3
    inDegree[3] = 4 - 1 = 3
    remainingNodes = 6 - 1 = 5
  
  Process 1:
    Neighbor: 3
    inDegree[3] = 3 - 1 = 2
    remainingNodes = 5 - 1 = 4
  
  Process 2:
    Neighbor: 3
    inDegree[3] = 2 - 1 = 1
    remainingNodes = 4 - 1 = 3
  
  Process 5:
    Neighbor: 4
    inDegree[4] = 2 - 1 = 1
    remainingNodes = 3 - 1 = 2
  
  New leaves: [3, 4] (both have degree 1 now)
  Leaves queue: [3, 4]

Step 4: Check Condition
  remainingNodes = 2 ≤ 2 → Stop

Step 5: Return Centers
  Result: [3, 4]

Visual Representation:

Initial:         After 1st iteration:
    0                 
    |                 
    3                 3
   /|\               / \
  1 2 4             4
        \             
         5           

Centers: 3 and 4 (both are valid MHT roots)

Complexity Analysis:

Time Complexity: O(n)
- Building graph: O(n)
- Peeling leaves: O(n) - each node processed once
- Overall: O(n)
Space Complexity: O(n)
- Adjacency list: O(n)
- Degree array: O(n)
- Queue: O(n)

Key Insights

Tree Centers: At most 2 centers exist (middle of longest path)
Peeling Leaves: Repeatedly remove leaves until centers remain
Batch Processing: Process all leaves at same level together
Convergence: Always converges to 1 or 2 nodes
MHT Roots: Centers minimize maximum distance to any leaf

Edge Cases

Single node: n = 1 → return [0]
Two nodes: n = 2, edges = [[0,1]] → return [0,1] (both are centers)
Linear tree: n = 4, edges = [[0,1],[1,2],[2,3]] → return [1,2] (middle nodes)
Star tree: n = 4, edges = [[0,1],[0,2],[0,3]] → return [0] (center)
Balanced tree: Returns 1 or 2 centers depending on structure

Common Mistakes

Not handling single node: Forgetting edge case n == 1
Wrong stopping condition: Should stop when remainingNodes <= 2, not == 0
Not batch processing: Processing leaves one at a time instead of by level
Wrong degree update: Not updating degrees correctly when removing leaves
Not tracking remaining nodes: Forgetting to decrement remainingNodes

Alternative Approaches

Approach 2: Two-Pass BFS (Find Diameter)

Find the longest path (diameter) in the tree, then return the middle node(s).

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n == 1) return {0};
        
        vector<vector<int>> adj(n);
        for(auto& e: edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }
        
        // First BFS: Find one end of diameter
        int u = bfs(adj, 0, n).first;
        
        // Second BFS: Find other end and path
        auto [v, parent] = bfs(adj, u, n);
        
        // Find middle node(s) of diameter
        vector<int> path;
        int curr = v;
        while(curr != -1) {
            path.push_back(curr);
            curr = parent[curr];
        }
        
        int len = path.size();
        if(len % 2 == 0) {
            return {path[len/2 - 1], path[len/2]};
        } else {
            return {path[len/2]};
        }
    }
    
private:
    pair<int, vector<int>> bfs(vector<vector<int>>& adj, int start, int n) {
        queue<int> q;
        vector<int> parent(n, -1);
        vector<bool> visited(n, false);
        q.push(start);
        visited[start] = true;
        int farthest = start;
        
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            farthest = u;
            for(int v: adj[u]) {
                if(!visited[v]) {
                    visited[v] = true;
                    parent[v] = u;
                    q.push(v);
                }
            }
        }
        return {farthest, parent};
    }
};

Time Complexity: O(n) - Two BFS passes
Space Complexity: O(n)

Approach 3: Two-Pass DFS (Find Diameter)

Similar to BFS approach but using DFS to find the diameter. Uses recursion to find farthest nodes.

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n == 1) return {0};
        
        vector<vector<int>> adj(n);
        for(auto& e: edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }
        
        // First DFS: Find one end of diameter
        int farthestNode = 0;
        int maxDist = 0;
        vector<int> parent1(n, -1);
        dfs(adj, 0, -1, 0, farthestNode, maxDist, parent1);
        int u = farthestNode;
        
        // Second DFS: Find other end and path
        farthestNode = u;
        maxDist = 0;
        vector<int> parent2(n, -1);
        dfs(adj, u, -1, 0, farthestNode, maxDist, parent2);
        int v = farthestNode;
        
        // Reconstruct path from u to v
        vector<int> path;
        int curr = v;
        while(curr != -1) {
            path.push_back(curr);
            curr = parent2[curr];
        }
        
        // Find middle node(s) of diameter
        int len = path.size();
        if(len % 2 == 0) {
            return {path[len/2 - 1], path[len/2]};
        } else {
            return {path[len/2]};
        }
    }
    
private:
    void dfs(vector<vector<int>>& adj, int u, int parent, int dist, 
             int& farthestNode, int& maxDist, vector<int>& parentArr) {
        parentArr[u] = parent;
        
        if(dist > maxDist) {
            maxDist = dist;
            farthestNode = u;
        }
        
        for(int v: adj[u]) {
            if(v == parent) continue;
            dfs(adj, v, u, dist + 1, farthestNode, maxDist, parentArr);
        }
    }
};

Time Complexity: O(n) - Two DFS passes
Space Complexity: O(n) - Recursion stack

Algorithm Explanation:

First DFS: Start from any node (0), find the farthest node u by tracking distance
Second DFS: Start from u, find the farthest node v and build path using parent array
Find Centers: Middle node(s) of the path from u to v are the centers

Key Points:

DFS recursively explores all paths from a starting node
Tracks the farthest node and maximum distance encountered
Parent array allows path reconstruction

Approach 4: DFS with Height Calculation

Calculate height of tree when rooted at each node, return nodes with minimum height. This is less efficient but demonstrates the problem definition directly.

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n == 1) return {0};
        
        vector<vector<int>> adj(n);
        for(auto& e: edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }
        
        int minHeight = INT_MAX;
        vector<int> result;
        
        // Try each node as root
        for(int root = 0; root < n; root++) {
            int height = dfs(adj, root, -1);
            if(height < minHeight) {
                minHeight = height;
                result = {root};
            } else if(height == minHeight) {
                result.push_back(root);
            }
        }
        
        return result;
    }
    
private:
    int dfs(vector<vector<int>>& adj, int u, int parent) {
        int maxHeight = 0;
        for(int v: adj[u]) {
            if(v == parent) continue;
            maxHeight = max(maxHeight, dfs(adj, v, u));
        }
        return maxHeight + 1;
    }
};

Time Complexity: O(n²) - For each node, DFS takes O(n)
Space Complexity: O(n) - Recursion stack

Note: This approach is less efficient (O(n²)) compared to peeling leaves (O(n)), but it directly implements the problem definition.

Comparison:

Approach	Time	Space	Complexity	Notes
Peeling Leaves (BFS)	O(n)	O(n)	Low	Most intuitive, recommended
Two-Pass BFS	O(n)	O(n)	Medium	Directly finds diameter
Two-Pass DFS	O(n)	O(n)	Medium	Similar to BFS, uses recursion
DFS Height Calculation	O(n²)	O(n)	Low	Direct implementation, less efficient

LC 207: Course Schedule - Topological sort
LC 210: Course Schedule II - Topological sort ordering
LC 310: Minimum Height Trees - This problem
LC 323: Number of Connected Components - Graph connectivity

This problem demonstrates the Peeling Leaves pattern for finding tree centers. The key insight is that minimum height trees have their roots at the center(s) of the longest path, which can be found by repeatedly removing leaves until 1 or 2 nodes remain.

Robina Li

310. Minimum Height Trees

310. Minimum Height Trees

Problem Statement

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Solution Approach

Key Insights:

Algorithm:

Solution

Solution: Peeling Leaves (Topological Sort)

Algorithm Explanation:

Why This Works:

Example Walkthrough:

Complexity Analysis:

Key Insights

Edge Cases

Common Mistakes

Alternative Approaches

Approach 2: Two-Pass BFS (Find Diameter)

Approach 3: Two-Pass DFS (Find Diameter)

Approach 4: DFS with Height Calculation

Related Posts

Recent Posts

310. Minimum Height Trees

Problem Statement

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Solution Approach

Key Insights:

Algorithm:

Solution

Solution: Peeling Leaves (Topological Sort)

Algorithm Explanation:

Why This Works:

Example Walkthrough:

Complexity Analysis:

Key Insights

Edge Cases

Common Mistakes

Alternative Approaches

Approach 2: Two-Pass BFS (Find Diameter)

Approach 3: Two-Pass DFS (Find Diameter)

Approach 4: DFS with Height Calculation

Related Problems

Related Posts

Recent Posts