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 labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi 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: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.
Example 2:
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] Output: [3,4]
Constraints:
1 <= n <= 2 * 104edges.length == n - 10 <= ai, bi < nai != bi(ai, bi) are distinct.This approach uses an iterative method to trim the leaf nodes layer by layer until you are left with the centermost nodes, which are the roots of the Minimum Height Trees.
The idea is similar to peeling layers of an onion from the outside to the inside. The process stops when there are no more than two nodes left.
The C solution describes trimming nodes from the outermost layer (leaves), updating degrees, and reducing the graph until finding potential centroids. This is implemented using arrays to keep track of each node's neighbors and queue for processing leaves.
C++
Time Complexity: O(n), since each node and edge is processed once.
Space Complexity: O(n), for storing edges and nodes’ degrees.
This technique applies two breadth-first searches (BFS). Start from any node, find the farthest node to determine a tree diameter. From this end node, perform another BFS to determine the second endpoint. The center of the path between these endpoints, which are the potential MHT roots, is found.
In the Java solution, adjacency sets represent connections with degree checks for leaves. The while loop prunes tree leaves iteratively until potential centroids, interpreted as MHTs, are left.
Python
Time Complexity: O(n), for initializing and iterating over nodes.
Space Complexity: O(n), due to graph adjacency representations and queue processing.
| Approach | Complexity |
|---|---|
| Trim the Leaves Iteratively | Time Complexity: O(n), since each node and edge is processed once. |
| Utilize Two BFS Runs | Time Complexity: O(n), for initializing and iterating over nodes. |
Minimum Height Trees | Live Coding with Explanation | Leetcode #310 • Algorithms Made Easy • 32,125 views views
Watch 9 more video solutions →Practice Minimum Height Trees with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor