Mar 20, 2026 📖 7 min read

Last updated on Apr 2, 2026

Minimum Height Trees — Coding Interview Walkthrough

Q: How does Topological Sorting identify Minimum Height Trees optimally?

By conceptually viewing the node mapping as an expanding network, you iteratively prune the absolute outermost leaf nodes possessing exactly one connection at each BFS iteration. You essentially "burn" the graph directly from the exterior moving inward until you reach the centralized root survivors.

Q: What is the optimal execution time for calculating the Minimum Height Trees?

Because tracing all inward edges systematically hits every node mapping and their subsequent undirected pairings uniquely, the operation limits structurally at O(V + E) time boundaries safely dodging brute-force O(N^2) paths.

By intervu.dev

The core approach: Minimum Height Trees is solved with iterative leaf pruning in O(n) time and O(n) space. Repeatedly remove all current leaf nodes (degree 1) from the graph, layer by layer, until 1 or 2 nodes remain. The remaining nodes are always the centroids and are guaranteed to be the roots of minimum height trees.

You’re in a coding interview. The interviewer says: “Given a tree with n nodes, find all roots that minimize the height.” You know that brute-force BFS from every node would work, but it’s O(n^2). The efficient approach is less obvious: iteratively trim leaves until 1 or 2 nodes remain. Those remaining nodes are the centers of the tree, the roots of all Minimum Height Trees. LeetCode #310.

This walkthrough covers why leaf trimming works, the connection to the tree’s diameter, and the implementation details that trip up candidates.

Already know how to solve Minimum Height Trees? Try a Minimum Height Trees mock interview on Intervu →

The Problem

Given a tree of n nodes labeled 0 to n-1 as an undirected graph (edges), find all nodes that form roots of Minimum Height Trees (MHTs). Trees with those roots have the minimum possible height. There are at most 2 such roots. (LeetCode #310)

Example 1

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

Output [1]

Node 1 is the center. Rooting the tree at node 1 gives height 1. Rooting at any leaf (0, 2, or 3) gives height 2.

Example 2

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

Output [3, 4]

Both nodes 3 and 4 are centers. They’re adjacent, each giving a tree of height 2.

Tree with center node highlighted as MHT root after leaf trimming.

What Interviewers Are Actually Testing

Minimum Height Trees tests whether you can move beyond brute force and recognize a graph-theoretic property: the optimal roots are always the center(s) of the tree’s longest path.

Skill	What Interviewers Observe
Topological/leaf trimming insight	Do you recognize the iterative leaf-removal approach?
At most 2 roots	Do you know there are always at most 2 MHT roots?
Degree tracking	Do you use degree counts to identify current leaves?
BFS-like layered removal	Do you process all current leaves at once per round?
Edge case: n=1	Do you return `[0]` for a single node?

Step 1: Clarifying Questions

Is the input guaranteed to be a valid tree? Yes. n-1 edges, no cycles, fully connected. This means every node is reachable.
Can n be 1? Yes. A single node is its own root. Return [0].
Can n be 2? Yes. Both nodes are leaves and both are MHT roots. Return [0, 1].
Are there at most 2 MHT roots? Always. The MHT roots are the center(s) of the tree’s diameter. A path has either one center (odd length) or two (even length).

Step 2: A First (Non-Optimal) Idea

BFS from every node to compute the tree height when rooted at that node. Return the node(s) with the minimum height.

from collections import defaultdict, deque

def findMinHeightTrees_brute(n, edges):
    if n == 1:
        return [0]
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    def bfs_height(root):
        visited = {root}
        queue = deque([root])
        height = -1
        while queue:
            height += 1
            for _ in range(len(queue)):
                node = queue.popleft()
                for neighbor in adj[node]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
        return height

    heights = [bfs_height(i) for i in range(n)]
    min_h = min(heights)
    return [i for i, h in enumerate(heights) if h == min_h]

Approach	Time	Space
BFS from every node	O(n^2)	O(n)
Leaf trimming	O(n)	O(n)

Step 3: The Key Insight

The roots of MHTs are the “centers” of the tree, the midpoint(s) of its longest path (diameter). To find them, iteratively trim all current leaves until 1 or 2 nodes remain. Those are the MHT roots. This works because leaves can never be optimal roots: for any leaf, its neighbor is always a better root (strictly lower height).

The algorithm is analogous to topological sort on an undirected tree: peel off the outermost layer (leaves) repeatedly, and what remains is the core.

Step 4: Optimal Strategy

Build an adjacency set for each node.
Identify all initial leaves (nodes with degree 1).
While more than 2 nodes remain:
- Remove all current leaves and their edges.
- Any neighbor whose degree drops to 1 becomes a new leaf.
Return the remaining 1 or 2 nodes.

Python Implementation

from collections import defaultdict, deque

def findMinHeightTrees(n: int, edges: list[list[int]]) -> list[int]:
    if n == 1:
        return [0]

    adj = defaultdict(set)
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)

    # Initialize leaves (degree 1)
    leaves = deque([node for node in range(n) if len(adj[node]) == 1])
    remaining = n

    while remaining > 2:
        remaining -= len(leaves)
        new_leaves = deque()
        for leaf in leaves:
            neighbor = adj[leaf].pop()
            adj[neighbor].discard(leaf)
            if len(adj[neighbor]) == 1:
                new_leaves.append(neighbor)
        leaves = new_leaves

    return list(leaves)

Why this is interview-friendly:

Set-based adjacency for O(1) removal. Using set instead of list makes discard O(1). With a list, removal is O(degree).
remaining > 2 as the loop condition. This correctly handles both odd-diameter (1 center) and even-diameter (2 centers) cases.
Each node is processed exactly once as a leaf. The algorithm never revisits nodes.

Time & Space Complexity

	Time	Space
Minimum Height Trees	O(n)	O(n)

Each node is removed as a leaf exactly once. Building the adjacency sets is O(n). Total work is linear.

Common Interview Mistakes

Not handling n == 1. A single node has no edges. The leaf-finding loop produces an empty list. Return [0] explicitly.
Brute-forcing BFS from every node. Running BFS from each node to measure height is O(n^2). The leaf-trimming approach is O(n). Always mention the brute force first, then explain why it’s too slow.
Stopping at remaining == 1 only. Stop when remaining <= 2. Two nodes can both be MHT roots when they’re equidistant from both ends of the diameter.
Using a list instead of a set for adjacency. Removal from a list is O(degree), making the overall algorithm O(n * max_degree). Use set() for O(1) removal.
Not counting remaining correctly. Decrement remaining by the number of leaves before processing them. If you decrement inside the leaf-processing loop, you’ll stop one round too early or too late.

What a Strong Candidate Sounds Like

“The MHT roots are the center(s) of the tree’s longest path, at most two nodes. I find them by repeatedly trimming leaves: initialize a queue of all degree-1 nodes, remove them and their edges, and collect any new leaves. Repeat until 1 or 2 nodes remain. O(n) time, O(n) space.”

Example Interview Dialogue

Interviewer: Why can a leaf never be an MHT root?

Candidate: Consider any leaf L and its only neighbor P. If we root the tree at L, the height includes the entire subtree hanging off P plus the edge from L to P. If we root at P instead, that subtree height stays the same but we eliminate the extra edge. So P always produces a height at most as high as L, and often strictly lower. This means we can safely discard all leaves.

Interviewer: Why at most 2 centers?

Candidate: The centers are the midpoint(s) of the tree’s diameter (longest path). A path of odd length has one midpoint; a path of even length has two adjacent midpoints. Since a tree has a unique diameter, there are always 1 or 2 centers.

Course Schedule (LeetCode #207). Topological sort / leaf trimming on a directed graph. Same peeling-layers pattern.
Number of Islands (LeetCode #200). BFS/DFS on a grid graph.
Clone Graph (LeetCode #133). Graph traversal and reconstruction.

Frequently Asked Questions

How does Topological Sorting identify Minimum Height Trees optimally?

By conceptually viewing the node mapping as an expanding network, you iteratively prune the absolute outermost leaf nodes possessing exactly one connection at each BFS iteration. You essentially “burn” the graph directly from the exterior moving inward until you reach the centralized root survivors.

What is the optimal execution time for calculating the Minimum Height Trees?