The O(n) Club: Minimum Height Trees, or How to Avoid Roast CPU

The O(n) Club: Minimum Height Trees, or How to Avoid Roast CPU

⚡ TL;DR

If you’re about to brute-force every possible root in a tree to find the lowest height, stop, put the coffee down, and peel your tree like a fancy algorithmic onion. Strip away the leaves, round by round, and what remains is your coveted centroid—or perhaps two. These are your minimum height tree roots. Java code for the impatient:

// Don't fry your server with O(n^2)
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    if (n <= 2) return IntStream.range(0, n).boxed().collect(Collectors.toList());
    List<Set<Integer>> g = new ArrayList<>();
    for (int i = 0; i < n; i++) g.add(new HashSet<>());
    for (int[] e : edges) {
        g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]);
    }
    List<Integer> leaves = new ArrayList<>();
    for (int i = 0; i < n; i++) if (g.get(i).size() == 1) leaves.add(i);
    int remain = n;
    while (remain > 2) {
        remain -= leaves.size();
        List<Integer> newL = new ArrayList<>();
        for (int leaf : leaves) {
            int neighbor = g.get(leaf).iterator().next();
            g.get(neighbor).remove(leaf);
            if (g.get(neighbor).size() == 1) newL.add(neighbor);
        }
        leaves = newL;
    }
    return leaves;
}

🧠 How Devs Usually Mess This Up

You, me, everyone at some point thinks: “Let’s check every node as the root, run BFS/DFS, then pick the one with the shortest height!” Congratulations, you just invented O(n²)—and maybe burned a laptop in the process. Also, classic mistake: counting nodes instead of edges for height. Don’t be that guy. And yes, it’s true: there are NEVER more than 2 centroids. Ever. Even if you squint at the tree sideways.

🔍 What’s Actually Going On

Pretend your tree is a sentient onion. Peel off the outer leaves (literally: nodes with one connection) repeatedly. As layers disappear, the graph shrinks inward. After several rounds, what’s left at the core? The centroids. In human terms: pick the most central point(s) to minimize the longest commute—like a boss who’s still reachable by every employee, or a CDN node your content-desperate cat video finally streams from in under a second.

🛠️ PseudoCode

• If the tree’s size <= 2, just return all nodes. Slightly boring edge case, but hey, we get paid to be careful.
  if (n <= 2) return all nodes;
• Make an adjacency list to represent all those awkward connections.
  List<Set<Integer>> graph = ...
• Find all current leaves—nodes with exactly one neighbor.
  leaves = nodes where degree == 1
• As long as more than 2 nodes remain:
  • Chop off the leaves.
  • Update every neighbor; if their degree drops to 1, they’re the next leaves.

while (numNodes > 2) {
    remove leaves;
    update neighbors;
    collect new leaves;
}

💻 The Code

import java.util.*;
import java.util.stream.*;
 public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n <= 2) return IntStream.range(0, n).boxed().collect(Collectors.toList());
         List<Set<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new HashSet<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
         List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; i++) if (graph.get(i).size() == 1) leaves.add(i);
        int remain = n;
        while (remain > 2) {
            remain -= leaves.size();
            List<Integer> newLeaves = new ArrayList<>();
            for (int leaf : leaves) {
                int neighbor = graph.get(leaf).iterator().next();
                graph.get(neighbor).remove(leaf);
                if (graph.get(neighbor).size() == 1) newLeaves.add(neighbor);
            }
            leaves = newLeaves;
        }
        return leaves;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Height is edge-count, not node-count. Save yourself an interview facepalm.
• Handle the dull edge cases: n == 0, n == 1, n == 2. Silence that test suite.
• Remove leaves properly each round! Otherwise you’re in an onion-loop from purgatory.
• Time/space: This approach is O(n), easy-breezy even if your ‘tree’ is a sprawling genealogy chart.

🧠 Interviewer Brain-Tattoo

“If you want a flat org chart, keep firing the leaves until only middle management survives.”