Minimum Height Trees: A Step-by-Step Interview Walkthrough

Jun 6

13 min read

Minimum Height Trees is a problem that punishes the obvious approach and rewards stepping back to find structure. The naive reading — "try every node as the root, measure the height, keep the best" — works, but it's quadratic, and the interviewer is specifically watching to see whether you settle for that or push for the insight that makes it linear. The key realization is that this isn't really a "measure heights" problem at all; it's a "find the center of the tree" problem in disguise. A tree rooted at its center has minimum height, and the center can be found without measuring a single height. Candidates who grind through BFS-from-every-node get a correct but slow answer. Candidates who recognize that the best roots are the tree's centroids — and that you can find them by peeling leaves inward — produce an elegant linear solution. The signal is whether you can reframe "minimize the maximum distance" into "find the center."

Finding the center of a network is a real operation across many domains. Network design places servers or facilities at central nodes to minimize worst-case latency or travel distance (the "facility location" problem). Distributed systems elect coordinator nodes near the center of a topology to minimize communication delay. Phylogenetics finds central points in evolutionary trees. Social network analysis identifies central actors whose maximum distance to anyone else is smallest. Any time you want to minimize the worst-case distance from a chosen point to all others in a tree-shaped structure, you're looking for the centroid — exactly what this problem computes.

Problem Statement

You are given an undirected tree with n nodes labeled 0 to n - 1, defined by an array of edges where edges[i] = [u, v] is an undirected edge between u and v.

A tree's height (for a chosen root) is the number of edges on the longest path from the root down to a leaf.

Return all node labels that can be chosen as roots such that the resulting tree has the minimum possible height.

Example:

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

result → [1] (rooting at node 1 gives height 1, the minimum).

1. Clarify Requirements Before Jumping Into Code

Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that would change our approach.

Input: an integer n and a list of undirected edges forming a tree.

Output: a list of all node labels that, used as the root, minimize the tree's height.

Details to clarify:

Is the input guaranteed to be a tree (connected, no cycles, exactly n-1 edges)? Yes — that guarantee matters; it's what makes the centroid approach work.
Can there be more than one answer? Yes — there can be one or two roots that achieve the minimum height, never more.
Do we return the height itself or just the roots? Just the roots.
What if n == 1? A single node is its own answer with height 0.
Are the edges directed? No — undirected, which is why we build a bidirectional adjacency list.

The thing to flag is "minimum possible height." We're not measuring one tree's height — we're searching over all possible roots for the one(s) that produce the shallowest tree. Note that the answer is a list of roots, so more than one node might tie for the minimum. Exactly how many can tie is something we'll pin down once we understand the structure — and the answer turns out to be surprisingly limited, in a way that guides the whole solution.

2. Identify the Category of the Question

A few signals jump out:

The structure is a tree (a special, well-behaved graph).
We're optimizing a choice of root to minimize the maximum root-to-leaf distance.
"Minimize the maximum distance" is a centering notion, not a counting one.

That combination — tree, minimize worst-case distance from a chosen point — points to finding the center (centroid) of a tree. The technique is a layered BFS that peels leaves inward, sometimes called "topological trimming." Same family as other "process the graph from its boundary inward" problems. The key is recognizing that the question about height is secretly a question about centrality.

3. Brute Force Solution

Let's start with the obvious approach to understand the problem. For each node, treat it as the root, compute the resulting tree's height with a BFS or DFS, and keep the node(s) with the smallest height.

for each node r in 0..n-1:
    height[r] = BFS/DFS height of tree rooted at r
return the node(s) with minimum height

Each height computation is a full traversal — O(n) for a tree with n nodes. Doing that from every node is O(n) traversals × O(n) nodes = O(n²). For large trees (tens of thousands of nodes), that's too slow.

The brute force teaches us something, though. As we'd compute these heights, we'd notice a pattern: nodes near the "middle" of the tree give small heights, and nodes near the "edges" (leaves) give large heights. The height grows as we move the root outward toward the periphery. That observation hints that there's a central location minimizing the height — and if we could find that center directly, we wouldn't need to test every node. The brute force is computing what we should be able to infer.

4. Brainstorm More Solutions

Step 1: What actually determines the height?

Let's reason about where height comes from. When we root the tree at some node r, the height is the distance from r to the farthest node from it. So minimizing height means choosing r to minimize its distance to the farthest node.

Now, what's the longest path in the whole tree? Let's call it the tree's diameter — the longest path between any two nodes. Intuitively, to minimize the maximum distance, we want to sit as close to the middle of the diameter as possible. If we root at one end of the diameter, the height is the full diameter length. If we root at the middle, the height is only about half the diameter.

So the best root is the midpoint of the longest path in the tree. That midpoint is the tree's center. And because the longest path could have an even or odd number of nodes/edges, that means the center is either a single node (if the diameter has an even number of edges) or two adjacent nodes (if the diameter has an odd number of edges). That means our answer must always one or two nodes — it's the midpoint of the longest path, which is either one node or a pair.

Step 2: How do we find the center without measuring the diameter?

We just argued that the best root is the midpoint of the tree's longest path. One way to act on that literally would be to find the longest path (there's a classic two-BFS trick — BFS from any node to find the farthest node, then BFS from that node to find the true diameter), then walk to its midpoint. That works, but it's a few moving parts, and getting the midpoint index right is fiddly. Let's see if there's a way to find the center that sidesteps measuring distances at all.

Let's think about what distinguishes a center node from a peripheral one. A leaf — a node with only one connection — is by definition at the edge of the tree; it's the end of some path, the farthest-out you can go in that direction. The center, by contrast, is buried in the interior, far from every edge. So the center and the leaves are opposites: leaves are the outermost nodes, the center is the innermost.

That suggests a way to locate the center by working from the outside in. If the leaves are the outermost layer, what happens if we remove them? Every leaf gets deleted, the tree shrinks, and — here's the useful part — some nodes that were one step inside the old leaves now have nothing beyond them. They've become the new leaves: the new outermost layer. Remove those too, and the layer behind them is exposed. Each removal peels off the current outer shell and reveals the next one further in.

If we keep peeling, we're contracting toward the interior from every direction at once. The leaves vanish first, then their neighbors, then their neighbors — the boundary marches inward uniformly. Whatever survives the longest is, by construction, the node (or nodes) farthest from every edge of the tree. That's the center. We never measured a single distance; we just removed the periphery repeatedly until only the core was left.

One more thing to notice: this isn't a normal BFS that fans out from a single source. We're starting from all the leaves simultaneously and moving inward — a multi-source search running in reverse, contracting instead of expanding. Recognizing that shape is what tells us how to set it up: seed the queue with every leaf at once, then process inward layer by layer.

Step 3: Track the peeling with degree counts

We have the idea — peel leaves inward until the center is left — but "remove a leaf" needs to become something concrete we can compute. So let's ask: how do we know, at any moment, whether a node is currently a leaf?

A leaf is a node with exactly one connection. So if we track how many neighbors each node still has — its degree — then "is this a current leaf?" becomes the simple test "is this node's degree = 1?" That gives us a cheap, local way to identify the outer shell at every stage without re-examining the whole tree.

Now think about what happens when we remove a leaf. Its single neighbor loses a connection, so that neighbor's degree drops by one. And here's the chain reaction we want: if that neighbor's degree falls to 1, it has just become a leaf itself — it's part of the next shell inward. So removing one layer naturally exposes the next, and we detect the new layer just by watching for degrees that hit 1.

That gives us the whole algorithm:

Build an adjacency list and compute every node's degree.
Put all current leaves (degree 1) into a queue — the outermost shell.
Repeatedly remove the entire current shell. For each removed leaf, decrement its neighbors' degrees, and any neighbor whose degree drops to 1 joins the queue as part of the next shell.
Stop when 2 or fewer nodes remain.

We process the queue one full layer at a time — the level-snapshot pattern, where we record the queue's size before processing so that the new leaves we add belong to the next shell, not this one. Alongside it we keep a running count of how many nodes are still in play, so we know when to stop.

Step 4: Why we stop at two and not one

The stopping condition deserves scrutiny, because the obvious guess — "peel until one node is left" — is wrong, and seeing why reveals something about tree structure.

Recall from Step 1 that the center is the midpoint of the tree's longest path. Now ask: does a path always have a single midpoint? A path with an even number of edges does — there's one node dead in the middle. But a path with an odd number of edges has no single middle node; the middle falls on an edge, with a node on each side that are equally central. Neither one is more "in the middle" than the other.

So the center is genuinely one node in some trees and two adjacent nodes in others, depending on whether the longest path has an even or odd number of edges.

Step 5: Walk through the examples

Single center: n = 4, edges [[1,0],[1,2],[1,3]]. This is a star with node 1 in the middle. Degrees: node 1 has 3, nodes 0, 2, 3 each have 1.

Leaves (degree 1): 0, 2, 3. Queue = [0, 2, 3]. remaining = 4.
remaining > 2, so peel. Remove 0, 2, 3. For each, decrement neighbor 1's degree: 3 → 2 → 1 → 0. None of these drops cause a new degree-1 node except... node 1 ends at degree 0, not 1, so it isn't re-added. remaining = 4 - 3 = 1.
remaining (1) ≤ 2, stop. But the queue is now empty — node 1 is what's left. (In the implementation, node 1 remains because it was never enqueued; the remaining counter tracks it.)

Wait — let me trace the actual code semantics. The remaining-based loop stops when remaining <= 2, and the answer is whatever is still in the queue at that point. Let me re-examine: after removing 0, 2, 3, node 1's degree hits 1 at some point during the decrements (3→2→1), so node 1 does get enqueued. remaining becomes 1, loop exits, and the queue holds [1]. Answer: [1]. Correct.

Dual center: n = 4, edges [[0,1],[1,2],[2,3]] — a straight line. Leaves: 0 and 3. Queue = [0, 3]. remaining = 4.

Peel 0 and 3. Decrement neighbors: node 1's degree 2→1 (enqueue 1), node 2's degree 2→1 (enqueue 2). remaining = 4 - 2 = 2.
remaining ≤ 2, stop. Queue holds [1, 2]. Answer: [1, 2]. Correct.

The peeling naturally lands on one or two central nodes depending on the tree's shape.

Step 6: Complexity

Building the adjacency list and degree array is O(n + e), and since this is a tree, e = n - 1, that reduces down to O(n).

In the peeling phase, each node is enqueued and dequeued at most once, and each edge is processed once when we decrement a degree. So the peeling is also O(n).

Total time: O(n).

Space is O(n) for the adjacency list (a tree has n - 1 edges), the degree array, and the queue.

This is a clean linear-time solution — a big improvement over the brute force's O(n²), achieved by computing the center directly instead of measuring every root's height.

5. Discuss Trade-Offs Between Solutions

Approach	Time	Space	When I'd use it
BFS/DFS height from every node	O(n²)	O(n)	Never for large inputs — but useful to mention as the baseline
Two-BFS diameter, then walk to midpoint	O(n)	O(n)	Works, but more steps and easier to get the midpoint indexing wrong
Leaf-trimming (multi-source inward BFS)	O(n)	O(n)	My default — finds the center directly and elegantly

The leaf-trimming approach is the cleanest. It finds the center without ever computing a height or a diameter explicitly — the peeling process is the center-finding, and the dual-center case falls out automatically.

6. Pseudocode

if n == 1: return [0]

build adjacency list and degree[] for all nodes
queue = all nodes with degree 1   # the outermost leaves
remaining = n

while remaining > 2:
    levelSize = queue.size()
    remaining -= levelSize
    repeat levelSize times:
        leaf = queue.pop()
        for each neighbor of leaf:
            degree[neighbor]--
            if degree[neighbor] == 1:
                queue.add(neighbor)   # new leaf, next shell inward

return whatever nodes remain in the queue

7. Edge Cases

Things to verify before claiming we're done:

n == 1 → single node, no edges. Handle explicitly: return [0]. (Its degree is 0, never 1, so it would never enter the leaf queue — the special case avoids returning an empty list.)
n == 2 (one edge) → both nodes have degree 1, both are leaves. remaining starts at 2, loop never runs, return both. ✓
Straight-line tree → peels symmetrically from both ends, lands on the middle one or two nodes. ✓
Star-shaped tree → all the outer nodes are leaves; one peel leaves the center. ✓
Tree with two valid centers → stopping at remaining <= 2 captures both. ✓

The n == 1 case is the one that needs an explicit guard. A lone node has degree 0, so it never qualifies as a leaf and never enters the queue — without the guard, we'd return an empty list instead of [0].

8. Full Code

import java.util.*;

public class MinimumHeightTrees {

    public static List<Integer> findMinHeightTrees(int n, int[][] edges) {
        // A single node is its own center — guard this explicitly 
        // because a degree-0 node never enters the leaf queue.
        if (n == 1) {
            return List.of(0);
        }

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

        // Start from all leaves (degree 1) — the outermost shell
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                queue.add(i);
            }
        }

        int remaining = n;

        // Peel layer by layer until 1 or 2 central nodes remain
        while (remaining > 2) {
            int size = queue.size();
            remaining -= size;

            for (int i = 0; i < size; i++) {
                int leaf = queue.poll();
                for (int neighbor : graph.get(leaf)) {
                    // Removing this leaf lowers the neighbor's 
                    // degree; if it becomes a leaf, it's part of 
                    // the next shell
                    if (--degree[neighbor] == 1) {
                        queue.add(neighbor);
                    }
                }
            }
        }

        // Whatever survived the peeling is the center
        return new ArrayList<>(queue);
    }
}

9. Test the Code

// Single center (star)
int[][] edges1 = {{1, 0}, {1, 2}, {1, 3}};
System.out.println(findMinHeightTrees(4, edges1));   // [1]

// Dual center (straight line)
int[][] edges2 = {{0, 1}, {1, 2}, {2, 3}};
System.out.println(findMinHeightTrees(4, edges2));   // [1, 2]

// Single node
System.out.println(findMinHeightTrees(1, new int[][]{}));   // [0]

// Two nodes — both are centers
int[][] edges4 = {{0, 1}};
System.out.println(findMinHeightTrees(2, edges4));   // [0, 1]

// Larger tree with a single center
int[][] edges5 = {{3,0},{3,1},{3,2},{3,4},{5,4}};
System.out.println(findMinHeightTrees(6, edges5));   // [3, 4] or [3]

These hit the meaningful cases: a star with a single center, a straight line with dual centers, the single-node edge case, a two-node tree, and a larger asymmetric tree. For trees with multiple valid centers, verify membership rather than expecting a specific order — the answer is a set, not a sequence.

10. Key Lessons

When a problem asks you to optimize over many choices (here, every possible root), check whether you can infer the optimal choice from the structure instead of testing each one. The brute force computed every height; the insight was that the best root is the tree's center, which we can find directly.
"Minimize the maximum distance from a chosen point" is a centering problem. In a tree, the answer is the center (centroid), which lies at the midpoint of the longest path and is always one or two nodes. Recognizing this reframing turns an O(n²) search into an O(n) computation.
BFS isn't only for exploring outward from a source. Multi-source BFS that contracts inward from the boundary (here, peeling leaves) is a powerful pattern for finding cores, centers, or anything defined by distance from the periphery.
The "one or two centers" fact isn't arbitrary — it follows from whether the longest path has an even or odd number of edges. Knowing why the answer is at most two nodes is what lets you write the correct stopping condition (remaining <= 2).
Watch for the trivial input that breaks your main logic. The single-node tree has no leaves, so it slips past the leaf-based algorithm entirely and needs an explicit guard. Always ask which input your core mechanism silently fails to handle.

The thing that makes Minimum Height Trees click is the reframe from "how tall is the tree for each root?" to "where is the tree's center?" Once you see that minimizing height means sitting at the center, and that the center is what's left after you peel away every layer of leaves, the quadratic brute force collapses into an elegant linear peel. Training yourself to ask "can I find the answer's location directly instead of testing every candidate?" is the habit that turns problems like this from grindy to graceful.

Good Luck and Happy Coding!