Minimum Height Trees
Problem Description
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 * 104
- edges.length == n - 1
- 0 <= ai, bi < n
- ai != bi
- All the pairs (ai, bi) are distinct.
- The given input is guaranteed to be a tree and there will be no repeated edges.
Solve it on LeetCode
Approaches
1. BFS with Degree Count
Intuition:
The problem of finding the minimum height trees (MHTs) in an undirected graph can be tackled by understanding that the roots of MHTs are the central nodes in the longest path of a tree. For trees, the diameter path has a central point/points which split the path into equal or nearly equal parts, minimizing height from these nodes.
The key is to iteratively remove leaf nodes (nodes with only one connection) layer by layer until only one or two nodes are left. These final nodes represent the root of the minimum height trees.
Steps:
- Graph Representation
- We first create an adjacency list to represent the graph as this will help us easily find neighbors of each node.
- Initial Setup:
- Identify nodes with only one connection (leaves).
- Use a queue to perform a Breadth-First Search (BFS) starting from these leaves.
- Iterative Leaf Removal:
- Repeatedly remove leaves level by level until one or two nodes remain.
- For each leaf removed, reduce the degree of its neighbor and if the degree becomes one, it becomes a leaf for the next level.
- Identify MHT Roots:
- When we can't remove any more edges (when the remaining pending nodes are 1 or 2), these nodes are the desired roots of MHTs.
Code:
- Time Complexity: O(n), where (n) is the number of nodes. Each node and edge is added and removed at most once from the list.
- Space Complexity: O(n). The space mainly depends on the graph structure and any auxiliary space used for tracking nodes and leaves.