📖 6 min read
Last updated on

Minimum Height Trees — Coding Interview Walkthrough

By intervu.dev

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.

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.

Already comfortable with the solution? Practice it in a mock interview →

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.

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

Step 1: Clarifying Questions

  1. Is the input guaranteed to be a valid tree? Yes. n-1 edges, no cycles, fully connected. This means every node is reachable.

  2. Can n be 1? Yes. A single node is its own root. Return [0].

  3. Can n be 2? Yes. Both nodes are leaves and both are MHT roots. Return [0, 1].

  4. 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]
ApproachTimeSpace
BFS from every nodeO(n^2)O(n)
Leaf trimmingO(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

  1. Build an adjacency set for each node.
  2. Identify all initial leaves (nodes with degree 1).
  3. While more than 2 nodes remain:
    • Remove all current leaves and their edges.
    • Any neighbor whose degree drops to 1 becomes a new leaf.
  4. 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

TimeSpace
Minimum Height TreesO(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

  1. Not handling n == 1. A single node has no edges. The leaf-finding loop produces an empty list. Return [0] explicitly.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

Practice This in a Mock Interview

Minimum Height Trees is a problem where the brute-force approach (BFS from every node) is obvious but too slow, and the efficient approach (leaf trimming) requires a non-trivial insight about tree structure. Articulating why leaves can never be optimal roots, and why the answer is always 1 or 2 nodes, is what separates a strong answer from a partial one.

Start a mock interview for Minimum Height Trees on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →