# Minimum Height Trees
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-height-trees)
Canonical: https://scaleengineer.com/dsa/problems/minimum-height-trees
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Graph
**Companies:** [Citadel](https://scaleengineer.com/companies/citadel), [PhonePe](https://scaleengineer.com/companies/phonepe), [Splunk](https://scaleengineer.com/companies/splunk), [Stackline](https://scaleengineer.com/companies/stackline)
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimum-height-trees/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/minimum-height-trees/image1.jpg) 

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

**Constraints:**

* `1 <= n <= 2 * 104`
* `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.

# Approaches
## Brute Force by Calculating Height for Each Node
The most straightforward approach is to iterate through every node, treat it as the root of the tree, and calculate the resulting tree's height. We keep track of the minimum height found so far and the list of nodes that achieve this height.
**Time:** O(N^2), where N is the number of nodes. For each of the N nodes, we perform a Breadth-First Search (BFS) to calculate the height, which takes O(N + E) = O(N) time (since E = N-1 for a tree). This results in a total time complexity of O(N * N) = O(N^2). · **Space:** O(N), where N is the number of nodes. We need O(N) space for the adjacency list and another O(N) for the data structures used in each BFS call (queue and visited array).
**Pros:** Simple to understand and implement.; Guaranteed to be correct if it runs within the time limit.
**Cons:** Highly inefficient due to its quadratic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints (n up to 2 * 10^4).
### Explanation
This method exhaustively checks every possibility. For each node in the tree, we assume it's the root and then determine the height of the resulting rooted tree. The height is defined as the longest path from the root to any leaf node. This can be calculated using a graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS). A BFS is natural here, as the height corresponds to the number of levels traversed. We maintain a variable to store the minimum height seen so far and a list of corresponding roots. If we find a node that results in a smaller height, we update the minimum and clear the list, adding the new node. If we find a node that results in the same minimum height, we just add it to our list of results.

```java
import java.util.*;

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

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

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

        for (int i = 0; i < n; i++) {
            int height = calculateHeight(i, n, adj);
            if (height < minHeight) {
                minHeight = height;
                mhtRoots.clear();
                mhtRoots.add(i);
            } else if (height == minHeight) {
                mhtRoots.add(i);
            }
        }
        return mhtRoots;
    }

    private int calculateHeight(int root, int n, List<List<Integer>> adj) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(root);
        boolean[] visited = new boolean[n];
        visited[root] = true;
        int height = -1;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            height++;
            for (int i = 0; i < levelSize; i++) {
                int u = queue.poll();
                for (int v : adj.get(u)) {
                    if (!visited[v]) {
                        visited[v] = true;
                        queue.offer(v);
                    }
                }
            }
        }
        return height;
    }
}
```
### Algorithm
- Build an adjacency list representation of the tree.
- Initialize `min_height` to a very large value and `mht_roots` to an empty list.
- Loop through each node `i` from `0` to `n-1`:
  - Consider `i` as the root.
  - Perform a Breadth-First Search (BFS) starting from `i` to find the height of the tree. The height is the number of levels in the BFS traversal.
  - If the calculated height `h` is less than `min_height`, update `min_height = h` and reset `mht_roots` to `[i]`.
  - If `h` is equal to `min_height`, add `i` to `mht_roots`.
- After checking all nodes, return `mht_roots`.

## Finding the Longest Path with Two Traversals
A more efficient approach is based on the property that the roots of Minimum Height Trees are the center(s) of the graph. The center(s) of a tree are the middle node(s) of its longest path. We can find a longest path by performing two tree traversals (like BFS or DFS).
**Time:** O(N), where N is the number of nodes. The algorithm consists of building an adjacency list (O(N)), two BFS traversals (each O(N)), and path reconstruction (O(N)). The total time is linear. · **Space:** O(N). Space is required for the adjacency list (O(N)), the BFS queue (O(N)), and arrays to store distances and parent pointers (O(N)).
**Pros:** Optimal O(N) time complexity.; Correctly identifies the center(s) of the tree by finding the longest path.
**Cons:** The implementation is more involved than the leaf-peeling approach, requiring two separate traversals and path reconstruction logic.; The proof of why this works (i.e., why the farthest node from an arbitrary node is an endpoint of a longest path) is not immediately obvious.
### Explanation
This method leverages a key insight about tree structures. Instead of calculating height from every node, we find the single longest path (also called the diameter) of the tree. The node or nodes that lie in the middle of this path will minimize the maximum distance to any other node in the tree, thus forming the roots of the MHTs. The algorithm to find this path involves two BFS runs:
1. The first BFS starts from any node and finds the node (`A`) at the greatest distance. This node `A` is guaranteed to be an endpoint of at least one longest path.
2. The second BFS starts from `A` and finds the node (`B`) at the greatest distance from it. The path from `A` to `B` is a longest path in the tree.
Once we have this path, we can easily find its midpoint(s) to get our answer.

```java
import java.util.*;

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

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

        // 1. Find one endpoint of a longest path
        int[] parent = new int[n];
        int[] dist = new int[n];
        bfs(0, n, adj, parent, dist);
        
        int endpoint1 = 0;
        for (int i = 0; i < n; i++) {
            if (dist[i] > dist[endpoint1]) {
                endpoint1 = i;
            }
        }

        // 2. Find the other endpoint and the longest path
        bfs(endpoint1, n, adj, parent, dist);
        
        int endpoint2 = 0;
        for (int i = 0; i < n; i++) {
            if (dist[i] > dist[endpoint2]) {
                endpoint2 = i;
            }
        }

        // 3. Reconstruct the longest path
        List<Integer> path = new ArrayList<>();
        int curr = endpoint2;
        while (curr != -1) {
            path.add(curr);
            curr = parent[curr];
        }

        // 4. Find the center(s)
        int pathLength = path.size();
        if (pathLength % 2 == 1) {
            return Collections.singletonList(path.get(pathLength / 2));
        } else {
            return Arrays.asList(path.get(pathLength / 2 - 1), path.get(pathLength / 2));
        }
    }

    private void bfs(int startNode, int n, List<List<Integer>> adj, int[] parent, int[] dist) {
        Arrays.fill(parent, -1);
        Arrays.fill(dist, -1);
        
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(startNode);
        dist[startNode] = 0;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    parent[v] = u;
                    queue.offer(v);
                }
            }
        }
    }
}
```
### Algorithm
- Build an adjacency list for the tree.
- **Step 1: Find an endpoint of a longest path.**
  - Start a BFS/DFS from an arbitrary node (e.g., node 0).
  - Find the node `A` that is farthest from the starting node. This node `A` is guaranteed to be one of the endpoints of a longest path in the tree.
- **Step 2: Find the longest path.**
  - Start a second BFS/DFS from node `A`.
  - Find the node `B` that is farthest from `A`. The path between `A` and `B` is a longest path.
  - During this second traversal, keep track of parent pointers to be able to reconstruct the path.
- **Step 3: Find the center(s).**
  - Reconstruct the longest path from `B` back to `A` using the parent pointers.
  - If the path has an odd number of nodes, the single middle node is the MHT root.
  - If the path has an even number of nodes, the two middle nodes are the MHT roots.

## Iterative Leaf Removal (Topological Sort Approach)
The most elegant and efficient solution involves iteratively removing the leaves of the tree. The intuition is that the nodes we are looking for must be the most 'central' ones. By repeatedly 'peeling' away the outermost layer of nodes (the leaves), we move closer to the center. The process continues until we are left with either one or two nodes, which are the roots of the MHTs.
**Time:** O(N), where N is the number of nodes. Building the graph and initial degrees takes O(N + E) = O(N). Each node and edge is processed exactly once during the leaf removal process. Thus, the overall time complexity is linear. · **Space:** O(N). We use an adjacency list (O(N)), a degree array (O(N)), and a queue that can store up to N-1 nodes in the worst case (a star graph).
**Pros:** Optimal O(N) time complexity.; Conceptually elegant and often considered easier to implement correctly than the longest path method.; Directly finds the centers without explicit path reconstruction.
**Cons:** The intuition might not be as immediately obvious as the brute-force method, but it's a standard graph algorithm pattern.
### Explanation
This approach is analogous to a topological sort. The key idea is that the nodes that are furthest from the center are the leaves of the tree. If we remove all leaves, the new leaves of the remaining graph are the nodes that were next to the original leaves. We can continue this process, removing layers of leaves, until we are left with the most central nodes. This process will always terminate with either one node (if the longest path has an odd number of nodes) or two adjacent nodes (if the longest path has an even number of nodes). These final remaining nodes are the roots of the Minimum Height Trees.

```java
import java.util.*;

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n <= 2) {
            List<Integer> result = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                result.add(i);
            }
            return result;
        }

        List<List<Integer>> adj = new ArrayList<>();
        int[] degrees = new int[n];
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adj.get(u).add(v);
            adj.get(v).add(u);
            degrees[u]++;
            degrees[v]++;
        }

        Queue<Integer> leaves = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (degrees[i] == 1) {
                leaves.offer(i);
            }
        }

        int remainingNodes = n;
        while (remainingNodes > 2) {
            int leavesCount = leaves.size();
            remainingNodes -= leavesCount;
            for (int i = 0; i < leavesCount; i++) {
                int leaf = leaves.poll();
                for (int neighbor : adj.get(leaf)) {
                    degrees[neighbor]--;
                    if (degrees[neighbor] == 1) {
                        leaves.offer(neighbor);
                    }
                }
            }
        }

        return new ArrayList<>(leaves);
    }
}
```
### Algorithm
- Handle the base case: if `n <= 2`, all nodes are MHT roots.
- Build an adjacency list and an array to store the degree of each node.
- Initialize a queue and add all leaf nodes (nodes with degree 1) to it.
- Keep track of the number of nodes remaining in the graph, initially `n`.
- While the number of remaining nodes is greater than 2:
  - Process all nodes currently in the leaf queue (this constitutes one layer).
  - For each leaf node removed:
    - Decrement the degree of its single neighbor.
    - If the neighbor's degree becomes 1, it is a new leaf, so add it to the queue for the next iteration.
- The loop terminates when 1 or 2 nodes are left. These nodes are the last ones to be processed and are the MHT roots remaining in the queue.

# Solutions
### Java

```java
class Solution { public List < Integer > findMinHeightTrees ( int n , int [][] edges ) { if ( n == 1 ) { return Collections . singletonList ( 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 ]; } Queue < Integer > q = new LinkedList <>(); 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 ; } }
```

### CPP

```cpp
class Solution { public: vector < int > findMinHeightTrees ( int n , vector < vector < int >>& edges ) { if ( n == 1 ) return { 0 }; vector < vector < int >> g ( n ); vector < int > degree ( n ); for ( auto & e : edges ) { int a = e [ 0 ], b = e [ 1 ]; g [ a ]. push_back ( b ); g [ b ]. push_back ( a ); ++ degree [ a ]; ++ degree [ b ]; } queue < int > q ; for ( int i = 0 ; i < n ; ++ i ) if ( degree [ i ] == 1 ) q . push ( i ); vector < int > ans ; while ( ! q . empty ()) { ans . clear (); for ( int i = q . size (); i > 0 ; -- i ) { int a = q . front (); q . pop (); ans . push_back ( a ); for ( int b : g [ a ]) if ( -- degree [ b ] == 1 ) q . push ( b ); } } return ans ; } };
```

### Python

```python
from typing import List , Set from collections import defaultdict class Solution : def findMinHeightTrees ( self , n : int , edges : List [ List [ int ]]) -> List [ int ]: if n == 1 : return [ 0 ] graph = defaultdict ( set ) for a , b in edges : graph [ a ]. add ( b ) graph [ b ]. add ( a ) # just check neighbours[] size, not indgree[] for each node leaves = [ i for i in range ( n ) if len ( graph [ i ]) == 1 ] while n > 2 : n -= len ( leaves ) new_leaves = [] for leaf in leaves : # should be only one in hashset pop(), because it's a leaf node neighbor = graph [ leaf ]. pop () graph [ neighbor ]. remove ( leaf ) if len ( graph [ neighbor ]) == 1 : new_leaves . append ( neighbor ) leaves = new_leaves return leaves ############### class Solution : def findMinHeightTrees ( self , n : int , edges : List [ List [ int ]]) -> List [ int ]: if n == 1 : return [ 0 ] g = defaultdict ( list ) degree = [ 0 ] * n for a , b in edges : g [ a ]. append ( b ) g [ b ]. append ( a ) degree [ a ] += 1 # not needed, just len(g[a]) is good enough, will update it in next round updating degree [ b ] += 1 q = deque () for i in range ( n ): if degree [ i ] == 1 : q . append ( i ) ans = [] while q : n = len ( q ) ans . clear () for _ in range ( n ): a = q . popleft () ans . append ( a ) for b in g [ a ]: degree [ b ] -= 1 if degree [ b ] == 1 : # final round only 2 left (a,b), then degree[b] here will be 0, and no more node enqueue q . append ( b ) return ans
```