Minimum Height Trees

Medium
458.

Minimum Height Trees

Minimum Height Trees is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Meta interviews.

A tree has n nodes labelled 0 through n - 1 and n - 1 undirected edges. Rooting it at any node produces a tree of some height.

Return every root that yields the minimum possible height, in ascending order.

Example 1

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

Example 2

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

Example 3

Input
n = 1, edges = []
Output
[0]

Constraints

  • 1 <= n <= 40
  • edges.length == n - 1
  • The input is guaranteed to be a tree.

Follow-up: There are at most two answers. Why can there never be three?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[]}
 */
var findMinHeightTrees = function(n, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Height Trees — Solution in Python, Java & C++

Minimum Height Trees solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Height Trees is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Meta interviews.

Problem statement

A tree has n nodes labelled 0 through n - 1 and n - 1 undirected edges. Rooting it at any node produces a tree of some height.

Return every root that yields the minimum possible height, in ascending order.

Example 1

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

Example 2

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

Example 3

Input: n = 1, edges = []
Output: [0]

Constraints

  • 1 <= n <= 40
  • edges.length == n - 1
  • The input is guaranteed to be a tree.

Follow-up: There are at most two answers. Why can there never be three?

Hints for Minimum Height Trees

  1. Hint 1

    The best roots sit at the centre of the tree's longest path, so peel inward from the outside.

  2. Hint 2

    Repeatedly strip off all current leaves, exactly like a topological sort on an undirected tree.

  3. Hint 3

    Stop when 2 or fewer nodes remain — those are the centroids.

How to solve Minimum Height Trees

Peel leaves layer by layer; the last one or two nodes standing are the centroids, which root the minimum-height trees.

Approach

  1. Return [0] for n = 1.
  2. Compute degrees; start with all degree-1 nodes as leaves.
  3. While more than 2 nodes remain, remove the leaves and collect neighbours whose degree drops to 1.
  4. Return the remaining nodes.

Why it works

The minimum-height root lies at the middle of every longest path; stripping leaves from all ends simultaneously shortens every longest path equally, so the survivors are the middle one (odd length) or two (even length).

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Rooting at each node and measuring is O(n²).

Reference solution

Python

def findMinHeightTrees(n: int, edges):
    if n == 1:
        return [0]
    adjacency = [[] for _ in range(n)]
    degree = [0] * n
    for a, b in edges:
        adjacency[a].append(b)
        adjacency[b].append(a)
        degree[a] += 1
        degree[b] += 1
    leaves = [i for i in range(n) if degree[i] == 1]
    remaining = n
    while remaining > 2:
        remaining -= len(leaves)
        nxt = []
        for leaf in leaves:
            for neighbour in adjacency[leaf]:
                degree[neighbour] -= 1
                if degree[neighbour] == 1:
                    nxt.append(neighbour)
        leaves = nxt
    return sorted(leaves)

Java

public static int[] findMinHeightTrees(int n, int[][] edges) {
    if (n == 1) return new int[]{0};
    List<List<Integer>> adjacency = new ArrayList<>();
    int[] degree = new int[n];
    for (int i = 0; i < n; i++) adjacency.add(new ArrayList<>());
    for (int[] e : edges) {
        adjacency.get(e[0]).add(e[1]);
        adjacency.get(e[1]).add(e[0]);
        degree[e[0]]++;
        degree[e[1]]++;
    }
    List<Integer> leaves = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (degree[i] == 1) leaves.add(i);
    }
    int remaining = n;
    while (remaining > 2) {
        remaining -= leaves.size();
        List<Integer> next = new ArrayList<>();
        for (int leaf : leaves) {
            for (int neighbour : adjacency.get(leaf)) {
                degree[neighbour]--;
                if (degree[neighbour] == 1) next.add(neighbour);
            }
        }
        leaves = next;
    }
    Collections.sort(leaves);
    int[] out = new int[leaves.size()];
    for (int i = 0; i < leaves.size(); i++) out[i] = leaves.get(i);
    return out;
}

C++

vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
    if (n == 1) return vector<int>{0};
    vector<vector<int>> adjacency(n);
    vector<int> degree(n, 0);
    for (const auto& e : edges) {
        adjacency[e[0]].push_back(e[1]);
        adjacency[e[1]].push_back(e[0]);
        degree[e[0]]++;
        degree[e[1]]++;
    }
    vector<int> leaves;
    for (int i = 0; i < n; i++) {
        if (degree[i] == 1) leaves.push_back(i);
    }
    int remaining = n;
    while (remaining > 2) {
        remaining -= (int) leaves.size();
        vector<int> next;
        for (int leaf : leaves) {
            for (int neighbour : adjacency[leaf]) {
                degree[neighbour]--;
                if (degree[neighbour] == 1) next.push_back(neighbour);
            }
        }
        leaves = next;
    }
    sort(leaves.begin(), leaves.end());
    return leaves;
}

JavaScript

var findMinHeightTrees = function(n, edges) {
    if (n === 1) return [0];
    const adjacency = [];
    const degree = [];
    for (let i = 0; i < n; i++) {
        adjacency.push([]);
        degree.push(0);
    }
    for (let i = 0; i < edges.length; i++) {
        adjacency[edges[i][0]].push(edges[i][1]);
        adjacency[edges[i][1]].push(edges[i][0]);
        degree[edges[i][0]]++;
        degree[edges[i][1]]++;
    }
    let leaves = [];
    for (let i = 0; i < n; i++) {
        if (degree[i] === 1) leaves.push(i);
    }
    let remaining = n;
    while (remaining > 2) {
        remaining -= leaves.length;
        const next = [];
        for (let i = 0; i < leaves.length; i++) {
            const leaf = leaves[i];
            for (let j = 0; j < adjacency[leaf].length; j++) {
                const neighbour = adjacency[leaf][j];
                degree[neighbour]--;
                if (degree[neighbour] === 1) next.push(neighbour);
            }
        }
        leaves = next;
    }
    return leaves.slice().sort(function(a, b) { return a - b; });
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)