Minimum Height Trees

Minimum Height Trees

1. What is this problem about?

The Minimum Height Trees problem is a unique graph challenge. You are given a tree (an undirected graph with no cycles) and you need to find all nodes that, when chosen as the root, produce a tree with the minimum possible height. The height of a tree is the maximum distance from the root to any leaf. Finding these "central" nodes is key to balancing the tree structure.

2. Why is this asked in interviews?

This question is a favorite at companies like Microsoft, PhonePe, and Adobe because it tests a candidate's ability to think about graph properties beyond basic traversals. The Minimum Height Trees interview question evaluates whether you can identify the "Centroid" of a tree. It requires a clever application of Topological Sort principles to an undirected graph, shifting the perspective from "top-down" to "outside-in."

3. Algorithmic pattern used

The algorithmic pattern used is a variant of Topological Sort (similar to Kahn's algorithm) applied to an undirected tree. The idea is to iteratively remove all leaf nodes (nodes with degree 1) until only one or two nodes remain. These remaining nodes are the centroids of the tree and will result in the Minimum Height Trees. This "Graph, BFS, Topological Sort interview pattern" is efficient with a time complexity of $O(N)$.

4. Example explanation

Consider a tree: $0-1, 1-2, 1-3$.

1. Initial leaves: [0, 2, 3] (all have degree 1).
2. Remove [0, 2, 3].
3. The only node left is 1. Result: [1]. If the tree was $0-1, 1-2, 2-3$:
4. Initial leaves: [0, 3].
5. Remove [0, 3]. Remaining: [1, 2].
6. Both 1 and 2 are leaves now. If we remove them, nothing is left. Result: [1, 2].

5. Common mistakes candidates make

A common error in the Minimum Height Trees coding problem is trying to calculate the height of the tree for every possible root using BFS/DFS. This results in an $O(N^2)$ solution, which is too slow for large graphs ($N=20,000$). Another mistake is not correctly managing the degrees of the nodes as leaves are removed, or failing to handle the base case of 1 or 2 nodes correctly.

6. Interview preparation tip

Master the "iterative leaf removal" technique. It's a powerful way to find the center of any tree structure. Remember that a tree can have at most two centroids. This "Graph Centroid pattern" is very useful for problems involving minimizing distances or balancing hierarchical data.