Minimum Height Trees

MEDIUM✓ CHIP-TIMEDLC #310 — FULL STATEMENT ↗

The drill: Given a tree of n nodes, pick every node that — if made the root — gives the shortest possible tree, measured by the longest path down from that root. There are at most two such nodes; return all of them, in any order.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A tree of n nodes arrives as a plain list of undirected edges, with no fixed root. The task is to figure out which node, if picked as the root, produces the shortest possible tree — measured by the longest path from that root down to any leaf.

Different roots can give wildly different heights for the same tree; rooting near either end of the tree's longest path always produces the tallest result, while rooting near the true middle produces the shortest.

At most two nodes can ever tie for that minimum height, and both would sit adjacent to each other at the tree's structural center. The answer is every node achieving that minimum, in any order.

EX 01

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

→ [1]

A STAR — THE HUB IS THE ONLY CENTER

EX 02

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

→ [3, 4]

TWO ADJACENT NODES TIE FOR CENTER

EX 03

n = 1 · edges = []

→ [0]

A SINGLE NODE IS ITS OWN CENTER

up to roughly ten thousand nodes
input is a valid tree: exactly n−1 edges, fully connected, no cycles
a single-node tree counts that node as its own answer
the result contains at most two node labels, order doesn't matter

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Rooting a tree at different nodes changes its height. The node that minimizes height sits as close as possible to every leaf — nowhere near the edges of the tree's longest path.

HINT 2 THE STRUCTURE

Rooting at either end of the tree's longest path gives the worst possible height. The best root, or two adjacent best roots, sit at the exact middle of that path — the tree's center.

HINT 3 ONE STEP FROM THE ANSWER

Repeatedly strip away all current leaves at once, layer by layer, the way an onion loses its skin. Whatever one or two nodes are left standing when the peeling stops are the tree's center.

COACH'S BOARD — THE PATTERN, STEP BY STEP

PEELING TO THE CENTERPATTERN · PEEL THE LEAVESn = 6 · edges: (3,0) (3,1) (3,2) (3,4) (4,5)

STEP 1

6 nodes. Repeatedly peel every current leaf — a degree-1 node — until 1 or 2 remain; those are the centers.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/minimum-height-trees.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]
        if n == 2:
            return [0, 1]

        graph = [set() for _ in range(n)]
        for a, b in edges:
            graph[a].add(b)
            graph[b].add(a)

        leaves = [i for i in range(n) if len(graph[i]) == 1]
        remaining = n
        while remaining > 2:
            remaining -= len(leaves)
            next_leaves = []
            for leaf in leaves:
                neighbor = graph[leaf].pop()
                graph[neighbor].discard(leaf)
                if len(graph[neighbor]) == 1:
                    next_leaves.append(neighbor)
            leaves = next_leaves

        return leaves

TIME O(V+E)SPACE O(V+E)PYTHON · RACE PACE · 25 LN

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]

        graph = collections.defaultdict(list)
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        def height_from(root):
            visited = {root}
            queue = collections.deque([root])
            depth = -1
            while queue:
                depth += 1
                for _ in range(len(queue)):
                    node = queue.popleft()
                    for nxt in graph[node]:
                        if nxt not in visited:
                            visited.add(nxt)
                            queue.append(nxt)
            return depth

        heights = [height_from(root) for root in range(n)]
        best = min(heights)
        return [i for i, h in enumerate(heights) if h == best]

TIME O(V·(V+E))SPACE O(V+E)PYTHON · TRAINING PACE · 27 LN

class Solution {
    public int[] findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return new int[] { 0 };
        if (n == 2) return new int[] { 0, 1 };

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

        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; i++) if (graph.get(i).size() == 1) leaves.add(i);

        int remaining = n;
        while (remaining > 2) {
            remaining -= leaves.size();
            List<Integer> nextLeaves = new ArrayList<>();
            for (int leaf : leaves) {
                int neighbor = graph.get(leaf).iterator().next();
                graph.get(leaf).remove(neighbor);
                graph.get(neighbor).remove(leaf);
                if (graph.get(neighbor).size() == 1) nextLeaves.add(neighbor);
            }
            leaves = nextLeaves;
        }

        int[] out = new int[leaves.size()];
        for (int i = 0; i < out.length; i++) out[i] = leaves.get(i);
        return out;
    }
}

TIME O(V+E)SPACE O(V+E)JAVA · RACE PACE · 33 LN

class Solution {
    public int[] findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return new int[] { 0 };

        List<List<Integer>> graph = new ArrayList<>();
        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]);
        }

        int[] heights = new int[n];
        for (int root = 0; root < n; root++) heights[root] = heightFrom(graph, n, root);

        int best = Integer.MAX_VALUE;
        for (int h : heights) best = Math.min(best, h);

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) if (heights[i] == best) result.add(i);
        int[] out = new int[result.size()];
        for (int i = 0; i < out.length; i++) out[i] = result.get(i);
        return out;
    }

    private int heightFrom(List<List<Integer>> graph, int n, int root) {
        boolean[] visited = new boolean[n];
        visited[root] = true;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.add(root);
        int depth = -1;
        while (!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            for (int s = 0; s < size; s++) {
                int node = queue.poll();
                for (int nxt : graph.get(node)) {
                    if (!visited[nxt]) {
                        visited[nxt] = true;
                        queue.add(nxt);
                    }
                }
            }
        }
        return depth;
    }
}

TIME O(V·(V+E))SPACE O(V+E)JAVA · TRAINING PACE · 46 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED