191. Minimum Height Trees
๐ LeetCode Problem: 310. Minimum Height Trees
๐ Difficulty: Medium
๐ท๏ธ Topics: Graph, BFS, Tree, Topological Sort, Tree Centers
Problem Statement
A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.
Given a tree of n nodes labeled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [aแตข, bแตข] indicates that there is an undirected edge between the two nodes aแตข and bแตข in the tree, you can choose any node of the tree as the root.
When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e., min(h)) are called minimum height trees (MHTs).
Return a list of all MHTs' root labels. You can return the answer in any order.
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
Example 1:
Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation:
Tree structure:
0
|
1
/ \
2 3
If root = 0: height = 3 (0โ1โ2 or 0โ1โ3)
If root = 1: height = 1 (1โ0, 1โ2, or 1โ3) โ
MINIMUM!
If root = 2: height = 3 (2โ1โ0 or 2โ1โ3)
If root = 3: height = 3 (3โ1โ0 or 3โ1โ2)
MHT roots: [1]
Example 2:
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]
Explanation:
Tree structure:
0 1 2
\ | /
\|/
3---4---5
If root = 3: height = 2 โ
If root = 4: height = 2 โ
Other roots: height > 2
MHT roots: [3, 4]
Constraints:
- 1 <= n <= 2 * 10โด
- edges.length == n - 1
- 0 <= aแตข, bแตข < n
- aแตข != bแตข
- All the pairs (aแตข, bแตข) are distinct.
- The given input is guaranteed to be a tree and there will be no repeated edges.
๐ณ Visual Understanding - The Complete Picture
The Problem We're Solving ๐ค
Given an undirected tree, find root(s) that minimize height: ๐ณ
Example tree (n=4):
0
|
1
/ \
2 3
Different roots, different heights:
Root at 0: Root at 1:
0 1
| /|\
1 0 2 3
/ \
2 3 Height = 1 โ
MINIMUM!
Height = 3
Root at 2: Root at 3:
2 3
| |
1 1
/ \ / \
0 3 0 2
Height = 3 Height = 3
Question: Which root(s) give minimum height? ๐ฏ
Answer: Node 1 with height 1! โ
Building Understanding Through Examples ๐
Example 1: Star graph (center wins)
Tree:
0
|
1---2
|
3
Rooted at 0: height = 3
Rooted at 1: height = 1 โ
CENTER!
Rooted at 2: height = 3
Rooted at 3: height = 3
MHT root: [1] (the center node)
Example 2: Linear chain (middle wins)
Tree: 0---1---2---3---4
Rooted at 0: height = 4
Rooted at 1: height = 3
Rooted at 2: height = 2 โ
MIDDLE!
Rooted at 3: height = 3
Rooted at 4: height = 4
MHT root: [2] (the center node)
Example 3: Even-length chain (two centers)
Tree: 0---1---2---3
Rooted at 1: height = 2 โ
Rooted at 2: height = 2 โ
MHT roots: [1, 2] (both center nodes!)
Visual Insight: Peeling Onion Layers ๐ง
Start:
0 1 2
\ | /
\|/
3---4---5
Level 0 (leaves): {0, 1, 2, 5}
Remove leaves:
3---4
Level 1 (new leaves): {3, 4}
These are the centers! โ
MHT roots: [3, 4]
Pattern: Remove leaves layer by layer
Last 1-2 nodes = centers!
The Pattern Emerges ๐ก
Key observations: ๐
1๏ธโฃ Tree Centers = MHT Roots ๐ฏ
The center(s) of the tree minimize height
At most 2 centers in any tree!
2๏ธโฃ Topological Sort Variation ๐
Like Kahn's algorithm
But remove LEAVES instead of zero in-degree
Process layer by layer!
3๏ธโฃ Peeling From Outside ๐ง
Start with leaf nodes (degree 1)
Remove them, find new leaves
Continue until 1-2 nodes remain
4๏ธโฃ Why At Most 2 Centers? ๐ค
If 3+ centers: one must be closer to periphery
Contradiction! Can have 1 or 2 only!
5๏ธโฃ Similar to Kahn's But Different ๐
Kahn's: directed graph, in-degree 0
MHT: undirected tree, degree 1 (leaves)
๐ง The Journey From Brute Force to Optimal
Part 1: The Obvious Try - "Try every root?" ๐ค
๐ญ First thought: "Root at each node, calculate height!"
Brute force:
For each node as root:
BFS/DFS to find max depth (height)
Track minimum height and corresponding roots
Return roots with minimum height
Example:
n = 4, edges = [[1,0],[1,2],[1,3]]
Root 0: BFS finds max depth = 3
Root 1: BFS finds max depth = 1 โ
Root 2: BFS finds max depth = 3
Root 3: BFS finds max depth = 3
Minimum = 1, root = [1]
Problem: TOO SLOW! ๐ฑ
Time complexity:
For each of n nodes: O(n) BFS/DFS
Total: O(nยฒ) ๐
For 20,000 nodes: 400,000,000 operations! โ
Can we do better? ๐ค
Part 2: The Realization - "Centers minimize height!" ๐ญ
๐ค Key insight: What makes a good root?
Think geometrically:
Best root = CENTER of the tree!
Why?
Center = equidistant from all extremes
Minimizes maximum distance to any node
= Minimizes height! ๐ฏ
Example:
Linear chain: 0---1---2---3---4
Center node 2:
Max distance to any node = 2
(2 to 0 or 2 to 4)
Non-center node 0:
Max distance to node 4 = 4
Much worse!
So the question becomes:
"How to find the CENTER of a tree?"
This is a CLASSIC graph theory problem! ๐
Part 3: The Algorithm - "Peel like an onion!" ๐ก
๐ค Finding tree centers: Layer-by-layer removal!
Algorithm (similar to topological sort):
1. Start with all leaf nodes (degree 1)
2. Remove leaves, find new leaves
3. Continue until 1-2 nodes remain
4. These are the centers! ๐ฏ
Why this works:
Leaves are farthest from center
Remove them, move one layer inward
Keep peeling until reaching center!
Example:
Tree:
0 1 2
\ | /
\|/
3---4---5
Degrees: [1, 1, 1, 3, 2, 1]
Leaves: {0, 1, 2, 5}
Round 1: Remove leaves {0, 1, 2, 5}
Remaining: {3, 4}
Update degrees: [-, -, -, 1, 1, -]
New leaves: {3, 4}
Round 2: Only 2 nodes left! STOP! โ
Centers: {3, 4}
Intuition: Squeeze from outside toward center! ๐ง
Part 4: The Implementation - "Track degrees like Kahn's!" ๐ก
๐ค Implementation details:
Similar to Kahn's algorithm structure:
1. Calculate degrees (undirected graph)
degree[i] = number of neighbors
2. Queue all leaves (degree 1)
Special case: single node (degree 0) is also a leaf!
3. BFS-style layer removal:
while (n > 2): // More than 2 nodes remain
size = queue.size()
n -= size // Remove this layer
for each leaf in current layer:
for each neighbor:
degree[neighbor]--
if degree[neighbor] == 1:
queue.add(neighbor) // New leaf!
4. Remaining nodes (1 or 2) are centers! ๐ฏ
Key differences from Kahn's:
- Undirected graph (degree, not in-degree)
- Stop at 1-2 nodes (not 0)
- Process by layers (reduce n)
Time: O(n) - visit each node once! โก
Much better than O(nยฒ)! ๐
Part 5: The Pattern - "Tree center finding!" ๐ฏ
โจ This is a TREE CENTER problem!
Pattern recognition:
โ
Undirected tree
โ
Find node(s) that minimize some property
โ
Center-based optimization
โ
Layer-by-layer BFS
Related concepts:
- Tree diameter (longest path)
- Tree centroid (decomposition)
- Tree center (this problem!)
Key theorem:
"A tree has at most 2 centers"
Proof sketch:
If 3+ centers existed:
They'd form a path
Middle one is closer to periphery
Contradiction!
So: 1 or 2 centers only! ๐ฏ
This problem teaches:
โ
Tree properties
โ
Center finding algorithm
โ
BFS variation (leaf removal)
โ
Topological sort extension
Beautiful problem! ๐
๐ฏ Approach: Layer-by-Layer Leaf Removal (BFS)
The Key Insight ๐ก
Use layer-by-layer leaf removal to find tree centers ๐ง . Calculate degrees for all nodes ๐. Queue leaves (degree 1), special case for single node ๐. Remove leaves layer by layer, update degrees, find new leaves ๐. Stop when 1-2 nodes remain - these are centers! ๐ฏ Centers = MHT roots โ . At most 2 centers in any tree! Time: O(n) โก, Space: O(n) ๐ฆ!
Elegant center-finding algorithm! โจ
Complete Implementation
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// LAYER-BY-LAYER LEAF REMOVAL (BFS) ๐ง
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// Peel leaves until reaching center(s)
// Centers = MHT roots!
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// EDGE CASE: Single node ๐ฑ
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
if (n == 1) {
return Collections.singletonList(0);
}
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// BUILD ADJACENCY LIST ๐๏ธ
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// TRACK DEGREES (undirected graph) ๐
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
int[] degree = new int[n];
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// Add edges (undirected - both directions)
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
graph.get(u).add(v);
graph.get(v).add(u);
degree[u]++;
degree[v]++;
}
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// FIND INITIAL LEAVES ๐
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// Leaves = nodes with degree 1
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
Queue<Integer> leaves = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (degree[i] == 1) {
leaves.offer(i);
}
}
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// PEEL LEAVES LAYER BY LAYER ๐ง
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
int remainingNodes = n;
while (remainingNodes > 2) {
int leavesCount = leaves.size();
remainingNodes -= leavesCount;
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// PROCESS CURRENT LAYER OF LEAVES ๐
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
for (int i = 0; i < leavesCount; i++) {
int leaf = leaves.poll();
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// UPDATE NEIGHBORS' DEGREES ๐
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
for (int neighbor : graph.get(leaf)) {
degree[neighbor]--;
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// CHECK IF NEIGHBOR BECAME A LEAF ๐
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
if (degree[neighbor] == 1) {
leaves.offer(neighbor);
}
}
}
}
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
// REMAINING 1-2 NODES ARE CENTERS! ๐ฏ
// โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
return new ArrayList<>(leaves);
}
}
Why This Works ๐ฏ
Leaves are farthest from center: ๐ - Degree 1 nodes are on periphery - Removing them moves inward - Layer-by-layer approach!
Centers minimize maximum distance: ๐ - After removing all layers - Only 1-2 nodes remain - These are equidistant from all periphery!
At most 2 centers: ๐ข - Theorem: Trees have 1 or 2 centers - Our algorithm finds them all - Return as list of MHT roots!
Using Set for efficiency: โก - Set.remove() is O(1) - Easy to check degree (size()) - Clean neighbor management!
๐ Detailed Dry Run
Let's trace the algorithm on Example 2:
n = 6
edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ SETUP โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
Build adjacency list from edges:
Edge [3,0]: 3โ0
Edge [3,1]: 3โ1
Edge [3,2]: 3โ2
Edge [3,4]: 3โ4
Edge [5,4]: 5โ4
Adjacency list (using Sets):
0: {3}
1: {3}
2: {3}
3: {0, 1, 2, 4}
4: {3, 5}
5: {4}
Tree visualization:
0 1 2
\ | /
\|/
3---4---5
Degrees:
Node 0: degree 1 (leaf) ๐
Node 1: degree 1 (leaf) ๐
Node 2: degree 1 (leaf) ๐
Node 3: degree 4
Node 4: degree 2
Node 5: degree 1 (leaf) ๐
Layer-by-Layer Removal ๐ง
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ ๐ INITIALIZATION โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฃ
โ Build adjacency list and track degrees: โ
โ โ
โ graph: โ
โ 0: [3] โ
โ 1: [3] โ
โ 2: [3] โ
โ 3: [0, 1, 2, 4] โ
โ 4: [3, 5] โ
โ 5: [4] โ
โ โ
โ degree: [1, 1, 1, 4, 2, 1] โ
โ โ
โ Find initial leaves (degree 1): โ
โ Node 0: degree 1 โ
Add to queue โ
โ Node 1: degree 1 โ
Add to queue โ
โ Node 2: degree 1 โ
Add to queue โ
โ Node 3: degree 4 โ โ
โ Node 4: degree 2 โ โ
โ Node 5: degree 1 โ
Add to queue โ
โ โ
โ leaves = [0, 1, 2, 5] โ
โ remainingNodes = 6 โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ ๐ง
ROUND 1: Remove first layer of leaves โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฃ
โ Check: remainingNodes > 2? (6 > 2) YES โ
โ โ
โ Current leaves: [0, 1, 2, 5] โ
โ leavesCount = 4 โ
โ remainingNodes = 6 - 4 = 2 โ
โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Process leaf 0: โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Neighbors: [3] โ
โ Update degree[3]: 4 โ 3 โ
โ Is degree[3] == 1? NO โ
โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Process leaf 1: โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Neighbors: [3] โ
โ Update degree[3]: 3 โ 2 โ
โ Is degree[3] == 1? NO โ
โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Process leaf 2: โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Neighbors: [3] โ
โ Update degree[3]: 2 โ 1 โ
NOW A LEAF! โ
โ Add 3 to queue โ
โ โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Process leaf 5: โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ Neighbors: [4] โ
โ Update degree[4]: 2 โ 1 โ
NOW A LEAF! โ
โ Add 4 to queue โ
โ โ
โ After Round 1: โ
โ leaves = [3, 4] โ
โ remainingNodes = 2 โ
โ degree: [-, -, -, 1, 1, -] โ
โ โ
โ Tree after removing outer layer: โ
โ 3---4 โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ ๐ฏ TERMINATION CHECK โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฃ
โ Check: remainingNodes > 2? โ
โ remainingNodes = 2 โ
โ 2 > 2? NO โ
โ
โ โ
โ STOP! Centers found! ๐ฏ โ
โ โ
โ leaves = [3, 4] โ
โ These are the tree centers! โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
FINAL RESULT ๐
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
โ ๐ FINAL RESULT: [3, 4] โ
โ โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฃ
โ โ
โ Tree centers found: nodes 3 and 4! ๐ฏ โ
โ โ
โ Verification - Height from each root: โ
โ โ
โ Root at 3: โ
โ 0 1 2 โ
โ \ | / โ
โ \|/ โ
โ 3---4---5 โ
โ โ
โ Max depth: 2 (3โ4โ5 or 3โ0) โ
โ
โ โ
โ Root at 4: โ
โ 4 โ
โ / \ โ
โ 3 5 โ
โ /|\ โ
โ 0 1 2 โ
โ โ
โ Max depth: 2 (4โ3โ0) โ
โ
โ โ
โ Both give height 2 - minimum possible! ๐ โ
โ โ
โ Other roots would have height > 2: โ
โ Root 0: height 3 โ
โ Root 1: height 3 โ
โ Root 2: height 3 โ
โ Root 5: height 3 โ
โ โ
โ MHT roots: [3, 4] โ
โ
โ โ
โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
๐ Key Observations:
-
Degree array tracks connectivity: ๐ Each node's degree updated as leaves removed
-
Two centers found: ๐ข Nodes 3 and 4 both minimize height
-
Stopping condition: ๐ฏ Stopped when 2 nodes remained
-
Degree decrements efficiently: โก No need to mutate graph, just track degrees
-
Consistent with topological sort: โ Same pattern as Course Schedule problems!
๐ Complexity Analysis
Time Complexity: O(n) โก
Where:
n = number of nodes
Analysis:
Build graph: O(n)
- n-1 edges in tree
- Each edge processed twice (undirected)
- O(n) total
Find initial leaves: O(n)
- Check degree of each node once
Layer-by-layer removal: O(n)
- Each node processed at most once
- Each edge removed at most once
- Total: O(n + edges) = O(n) for tree
Overall: O(n) + O(n) + O(n) = O(n) โก
Key insight:
Each node visited once
Each edge removed once
Linear time! ๐
Example: 20,000 nodes
Time: ~20,000 operations
vs O(nยฒ) brute force: 400,000,000!
20,000x faster! ๐
Space Complexity: O(n) ๐ฆ
Space usage:
1. Adjacency list: O(n) ๐๏ธ
- n sets (one per node)
- Total n-1 edges
- Each edge stored twice
- O(n) total
2. Queue: O(n) ๐
- Worst case: all leaves in queue
- In practice: much smaller
- O(n) worst case
3. Result list: O(1) โจ
- At most 2 centers
- Constant space
Total: O(n) + O(n) + O(1) = O(n) ๐ฆ
The O(n) is necessary:
Must store graph structure
Tree with n nodes has n-1 edges
Example: 20,000 nodes
Graph: ~40,000 entries (edges ร 2)
Queue: up to 20,000
Reasonable space! โ
๐ Related Problems & Patterns
Core Pattern: Tree Center Finding ๐ฏ
// Template for tree center finding
class Solution {
public List<Integer> findTreeCenters(int n, int[][] edges) {
// Edge case: single node
if (n == 1) return Collections.singletonList(0);
// Build adjacency list (undirected)
List<Set<Integer>> graph = buildGraph(n, edges);
// Find initial leaves (degree 1)
Queue<Integer> leaves = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (graph.get(i).size() == 1) {
leaves.offer(i);
}
}
// Remove leaves layer by layer
int remaining = n;
while (remaining > 2) {
int size = leaves.size();
remaining -= size;
for (int i = 0; i < size; i++) {
int leaf = leaves.poll();
int neighbor = graph.get(leaf).iterator().next();
graph.get(neighbor).remove(leaf);
if (graph.get(neighbor).size() == 1) {
leaves.offer(neighbor);
}
}
}
// Remaining nodes are centers
return new ArrayList<>(leaves);
}
}
When to Use This Pattern ๐ฏ
โ
Undirected tree structure
โ
Find central node(s)
โ
Minimize some distance/height property
โ
Layer-by-layer processing from periphery
โ
At most 2 solutions expected
Recognition triggers: ๐ - "Minimum height" in trees ๐ณ - "Find center(s)" ๐ฏ - Undirected tree given ๐ - Optimize root selection ๐ - Layer removal approach ๐ง
Key insight: Peel from outside to find center! ๐ก
Related LeetCode Problems ๐
Direct Applications:
-
Tree Diameter (LC 1245) - Medium ๐ โข What's similar: Tree structure, center-related ๐ณ โข What's different: Find longest path, not centers ๐ฏ โข Key insight: Two BFS or center-based approach! ๐ก
-
Sum of Distances in Tree (LC 834) - Hard ๐ โข What's similar: Tree structure, all roots considered ๐ณ โข What's different: Calculate sums for all roots efficiently ๐ โข Key insight: Rerooting technique! โก
-
Longest Path in DAG (various) - Medium/Hard ๐ฏ โข What's similar: Find extremes in graph structure ๐ โข What's different: Directed graph, different goal ๐ โข Key insight: Topological sort + DP! ๐
Pattern Evolution: ๐
Level 1: Tree Center Finding ๐ฏ โ HERE
โโ Minimum Height Trees (LC 310)
Level 2: Tree Properties ๐ณ
โโ Tree Diameter (LC 1245)
โโ Height of Binary Tree (LC 104)
โโ Maximum Depth (various)
Level 3: Tree Rerooting ๐
โโ Sum of Distances in Tree (LC 834)
โโ Count Good Nodes (LC 1339)
โโ Tree DP (various)
Comparison with Kahn's Algorithm โ๏ธ
Kahn's Algorithm (Topological Sort):
- Directed graph
- Remove nodes with in-degree 0
- Process all nodes
- Result: topological ordering
MHT (Tree Centers):
- Undirected tree
- Remove nodes with degree 1 (leaves)
- Stop at 1-2 nodes
- Result: center node(s)
Similarities:
โ
Layer-by-layer BFS
โ
Queue-based processing
โ
Degree tracking
โ
Remove and update pattern
Differences:
โ Directed vs undirected
โ In-degree vs degree
โ Process all vs stop early
โ Ordering vs center finding
Same pattern family, different application! ๐ฏ
๐ Quick Revision Notes
๐ฏ Core Concept
Minimum Height Trees finds tree centers using layer-by-layer leaf removal ๐ง . Build adjacency list (undirected), find leaves (degree 1) ๐. Remove leaves layer by layer, update degrees, find new leaves ๐. Stop when 1-2 nodes remain - these are centers = MHT roots! ๐ฏ Tree has at most 2 centers (theorem) โ . Similar to Kahn's but undirected tree + stop early ๐. Time: O(n) โก, Space: O(n) ๐ฆ. Peel from outside to center!
โก Quick Implementation
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
// Approach - BFS
return bfs(n, edges);
}
private List<Integer> bfs(int n, int[][] edges) {
// base case
if (n == 1) {
return Collections.singletonList(0);
}
// Step 1: create graph and indegrees array.
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
int[] indegrees = new int[n];
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// GOTCHA: same as before, but 2 times insert now as its undirected graph now.
for (int i = 0; i < edges.length; i++) {
graph.get(edges[i][0]).add(edges[i][1]);
graph.get(edges[i][1]).add(edges[i][0]);
indegrees[edges[i][0]]++;
indegrees[edges[i][1]]++;
}
// Step 2: find vertices which are leaf nodes (like indegrees with 1 value)
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (indegrees[i] == 1) {
queue.offer(i);
}
}
// Step 3: Explore till n <= 2. Checking quue empty is optional.
// Main logic: n > 2
while (!queue.isEmpty() && n > 2) {
// Explore all leaf nodes
int size = queue.size();
n = n - size; // GOTCHA: reduce the number of nodes to explore
for (int i = 0; i < size; i++) {
int node = queue.poll();
for (int neighbour : graph.get(node)) {
indegrees[neighbour]--;
if (indegrees[neighbour] == 1) { // leaf node
queue.offer(neighbour);
}
}
}
}
return new ArrayList<>(queue);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.findMinHeightTrees(4, new int[][] { { 1, 0 }, { 1, 2 }, { 1, 3 } }));
System.out.println(s.findMinHeightTrees(6, new int[][] { { 3, 0 }, { 3, 1 }, { 3, 2 }, { 3, 4 }, { 5, 4 } }));
}
}
๐ Key Insights
Why Centers Minimize Height: ๐
Geometric intuition:
Linear chain: 0---1---2---3---4
Root at 0 (edge):
Max distance: 0โ4 = 4
Height = 4
Root at 2 (center):
Max distance: 2โ0 or 2โ4 = 2
Height = 2 โ
MINIMUM!
Key insight:
Center = equidistant from extremes
Minimizes maximum distance
= Minimizes tree height! ๐ฏ
For any tree:
Best root is at center
Center minimizes "worst case" distance
Perfect for minimizing height! โจ
At Most 2 Centers Theorem: ๐ข
Theorem: Every tree has 1 or 2 centers.
Proof by contradiction:
Assume 3+ centers exist: A, B, C
Centers are equidistant from periphery:
distance(A, periphery) = d
distance(B, periphery) = d
distance(C, periphery) = d
A, B, C must form a path in tree:
A---B---C
But then B is closer to periphery than A or C!
(By triangle inequality)
Contradiction! โ
Therefore: At most 2 centers! โ
In practice:
Odd-length diameter: 1 center
Even-length diameter: 2 centers
Using Degree Array: ๐ก
Why track degrees explicitly?
For leaf removal:
Need to: check if node is a leaf (degree 1)
Need to: update degrees when removing edges
With Set (old approach):
graph.get(node).size() gives degree
Must remove edges: set.remove(neighbor)
With degree array (new approach):
degree[node] gives degree directly
Just decrement: degree[neighbor]--
Simpler and more consistent! โ
Advantages:
โ
Consistent with topological sort problems
โ
No need to remove edges from graph
โ
Cleaner degree tracking
โ
Same pattern as Course Schedule I/II
Example:
Initial: degree = [1, 3, 2, 1]
Process leaf 0, neighbor 1:
degree[1]-- โ 2
Process leaf 3, neighbor 1:
degree[1]-- โ 1 (now a leaf!)
Track degrees, don't mutate graph! ๐ฏ
Stop at 1-2 Nodes: ๐ฏ
Why stop when remaining > 2?
while (remaining > 2) {
// Remove layer
}
After loop:
remaining = 1 or 2
These are the centers!
Why not remaining > 1?
Would remove one of the two centers!
Why not remaining > 0?
Would try to remove all nodes!
remaining > 2 is perfect:
Stops at 1 node (odd diameter)
OR stops at 2 nodes (even diameter)
These are exactly the centers! ๐ฏ
Layer-by-Layer Processing: ๐ง
Key pattern: Process entire layer at once!
int size = leaves.size(); // Current layer size
remaining -= size; // Remove entire layer
for (int i = 0; i < size; i++) {
// Process leaf
// Find new leaves
}
Why process by layers?
Ensures we move inward uniformly
All leaves at same "distance" from center
Clean peeling pattern! ๐ง
Like BFS levels:
Level 0: Outer leaves
Level 1: Next leaves
...
Final level: Center(s)! ๐ฏ
๐ช Memory Aid
"Peel the onion layer by layer" ๐ง
"Leaves removed, centers stay" ๐
"One or two nodes at most" ๐ข
"These are centers, found at last" ๐ฏ โจ
โ ๏ธ Don't Forget
- Single node edge case - return [0] immediately! ๐ฑ
- Use Set for graph - faster removal operations! โก
- Stop at 1-2 nodes - not 0 or 1! ๐ข
- Process entire layer - track layer size! ๐ง
- Undirected edges - add both directions! ๐
- At most 2 centers - tree property! ๐
You've mastered Minimum Height Trees - tree center finding with leaf removal! ๐๐ณโจ