Minimum Height Trees - Practice Coding Problems

Minimum Height Trees - 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] = [aᵢ, bᵢ] indicates that there is an undirected edge between the two nodes aᵢ and bᵢ 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.

Input & Output

Example 1 — Basic Tree

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

› Output: [1]

💡 Note: Node 1 is connected to all other nodes. When 1 is root, max path length is 1 (1→0, 1→2, or 1→3). Any other root gives height 2.

Example 2 — Linear Tree

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

› Output: [3,4]

💡 Note: Both nodes 3 and 4 are centers. Root 3 gives max path 3→4→5 (length 2). Root 4 gives max path 0→3→4 or 1→3→4 (length 2).

Example 3 — Single Node

$ Input: n = 1, edges = []

› Output: [0]

💡 Note: Only one node exists, so it must be the root with height 0.

Constraints

1 ≤ n ≤ 2 × 10⁴
edges.length == n - 1
0 ≤ aᵢ, bᵢ < n
aᵢ ≠ bᵢ
All the pairs (aᵢ, bᵢ) are distinct
The given input is guaranteed to be a tree and there will be no repeated edges

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Undirected tree with nodes 0 to n-1

Try Different Roots

Each root choice gives different height

Find Minimum

Center nodes give minimum height

Key Takeaway

🎯 Key Insight: The center nodes of a tree (at most 2) always produce minimum height trees

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is that minimum height trees have their roots at the center nodes of the tree. The optimal approach uses BFS topological sort to remove leaf nodes layer by layer until only 1-2 center nodes remain. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try Every Root	O(n²)	O(n)	Try each node as root and calculate tree height using DFS
BFS Topological Sort (Optimal)	O(n)	O(n)	Remove leaf nodes layer by layer until 1-2 nodes remain

Brute Force - Try Every Root — Algorithm Steps

Step 1: Build adjacency list from edges
Step 2: For each node 0 to n-1, use it as root
Step 3: Perform DFS to find maximum depth from this root
Step 4: Track minimum height and collect nodes with minimum height

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create adjacency list from edges

Try Each Root

For each node, calculate height using DFS

Find Minimum

Return nodes with minimum height

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int dfs(int** graph, int* graphSize, int node, int parent) {
    int maxDepth = 0;
    for (int i = 0; i < graphSize[node]; i++) {
        if (graph[node][i] != parent) {
            int depth = 1 + dfs(graph, graphSize, graph[node][i], node);
            if (depth > maxDepth) {
                maxDepth = depth;
            }
        }
    }
    return maxDepth;
}

int* solution(int n, int** edges, int edgesSize, int* returnSize) {
    *returnSize = 0;
    if (n == 1) {
        int* result = (int*)malloc(sizeof(int));
        result[0] = 0;
        *returnSize = 1;
        return result;
    }
    
    // Build adjacency list
    int** graph = (int**)malloc(n * sizeof(int*));
    int* graphSize = (int*)calloc(n, sizeof(int));
    
    for (int i = 0; i < n; i++) {
        graph[i] = (int*)malloc(n * sizeof(int));
    }
    
    for (int i = 0; i < edgesSize; i++) {
        int a = edges[i][0], b = edges[i][1];
        graph[a][graphSize[a]++] = b;
        graph[b][graphSize[b]++] = a;
    }
    
    int minHeight = INT_MAX;
    int* result = (int*)malloc(n * sizeof(int));
    
    // Try each node as root
    for (int root = 0; root < n; root++) {
        int height = dfs(graph, graphSize, root, -1);
        if (height < minHeight) {
            minHeight = height;
            *returnSize = 1;
            result[0] = root;
        } else if (height == minHeight) {
            result[(*returnSize)++] = root;
        }
    }
    
    // Cleanup
    for (int i = 0; i < n; i++) {
        free(graph[i]);
    }
    free(graph);
    free(graphSize);
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %s", line);
    
    // Parse edges - simplified for this implementation
    int edgesSize = n - 1;
    int** edges = (int**)malloc(edgesSize * sizeof(int*));
    for (int i = 0; i < edgesSize; i++) {
        edges[i] = (int*)malloc(2 * sizeof(int));
        edges[i][0] = i;
        edges[i][1] = i + 1;
    }
    
    int returnSize;
    int* result = solution(n, edges, edgesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    for (int i = 0; i < edgesSize; i++) {
        free(edges[i]);
    }
    free(edges);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we perform DFS which takes O(n) time

⚠ Quadratic Growth

Space Complexity

O(n)

Adjacency list storage and DFS recursion stack

⚡ Linearithmic Space

95.0K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try Every Root — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler