Graph Theory37 sections · 1633 units
Open in Course

LeetCode 310 Minimum Height Trees - Problem Statement

Find roots that minimize tree height

Problem: Minimum Height Trees Task: Given a tree with nn nodes, return all nodes that, when chosen as root, minimize the height of the tree. The answer is the center (or centers) of the tree.

You need to find the middle of the longest path. Use the "peeling the onion" algorithm: repeatedly remove leaves until only 11 or 22 nodes remain. Each round, you strip every current leaf and reduce the tree. The nodes left at the end are the centers. This runs in O(n)O(n) time and O(n)O(n) space.