Approach Summary
Iteratively peel leaf nodes (degree 1) from the outside in. The last 1 or 2 remaining nodes are the roots of minimum height trees.
How to Recognize This Pattern
- "Find centers of the tree"
- Topological peeling: remove leaves until ≤ 2 nodes remain
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Tags
DFS BFS Graph Topological Sort