This problem requires finding nodes that, when chosen as roots, minimize the tree height. The most efficient approach uses iterative leaf removal based on indegree counts, effectively a topological sort on the tree. GhostInterview guides you through handling edge cases, BFS propagation, and correctly returning multiple MHT roots when applicable.
Problem Statement
You are given a tree with n nodes labeled from 0 to n - 1. The tree is represented as an array of n - 1 edges, where edges[i] = [ai, bi] indicates an undirected connection between nodes ai and bi. Any node can be chosen as the root, and the height of the resulting tree is determined by the longest path from the root to any leaf.
Your task is to identify all nodes that, when selected as roots, produce the minimum possible height of the tree. Return a list of all such root labels in any order. This problem emphasizes using graph indegree and topological ordering to iteratively remove leaves until reaching the tree centers.
Examples
Example 1
Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
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]
Example details omitted.
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.
Solution Approach
Initialize Graph and Indegree Counts
Construct an adjacency list for the tree and compute the degree of each node. Nodes with degree 1 are leaves and form the initial set for iterative removal, directly tying to the problem's indegree plus topological ordering pattern.
Iterative Leaf Removal
Perform BFS by removing leaves layer by layer. After removing current leaves, decrement the degrees of neighboring nodes and add new leaves to the queue. Continue until one or two nodes remain, which are guaranteed to be the MHT roots.
Return Minimum Height Tree Roots
The last remaining nodes after iterative leaf pruning are the centers of the tree. Collect and return these nodes as they represent all roots that minimize tree height.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) since each node and edge is processed once during leaf removal. Space complexity is O(n) for adjacency lists and degree tracking. BFS traversal ensures linear performance for trees of any valid size.
What Interviewers Usually Probe
- Candidate quickly identifies that leaf nodes can be pruned iteratively to find centers.
- Candidate uses degree counts and adjacency lists rather than naive height calculations.
- Candidate correctly returns all remaining nodes as potential MHT roots, handling multiple centers.
Common Pitfalls or Variants
Common pitfalls
- Failing to account for multiple centers; a tree can have up to two MHT roots.
- Incorrectly updating degrees or adjacency lists during iterative leaf removal.
- Attempting DFS from each node, resulting in O(n^2) time instead of O(n) BFS pruning.
Follow-up variants
- Weighted tree where edge lengths vary, requiring recalculation of height based on path sums.
- Finding MHT roots in a forest instead of a single connected tree.
- Limiting root selection to a subset of nodes rather than all nodes.
How GhostInterview Helps
- Guides you through BFS topological leaf removal to directly identify MHT roots.
- Highlights degree tracking and adjacency management, preventing common off-by-one errors.
- Ensures proper handling of trees with one or two centers to return correct root sets.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the maximum number of minimum height trees a single tree can have?
A tree can have at most two MHT roots, which correspond to the centers of the tree after iterative leaf removal.
Why does the leaf-removal approach guarantee finding all minimum height trees?
Removing leaves layer by layer converges to the central node(s), which by definition minimize height from any chosen root.
Can I use DFS to find minimum height trees?
DFS from each node is possible but inefficient; the BFS leaf-removal approach achieves O(n) time, which is optimal.
How do I handle trees with only one node?
A single-node tree trivially has itself as the only MHT root.
How does indegree and topological ordering apply to this problem?
Indegree counts identify leaves, and topological ordering via BFS ensures iterative pruning correctly identifies tree centers.
Need direct help with Minimum Height Trees instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Minimum Height Trees from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the length of the longest increasing path in a matrix with given movement constraints using graph techniques.
Open problem page#210 Course Schedule IISolve the 'Course Schedule II' problem using graph indegree and topological ordering, utilizing DFS or BFS to find the correct course order.
Open problem page#207 Course ScheduleDetermine if all courses can be completed by analyzing prerequisite dependencies using indegree tracking and topological sorting to detect cycles.
Open problem page