310. Minimum Height Trees
Minimum Height Trees (LeetCode 310) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph BFS - Topological Sort (Kahn's Algorithm) subpattern.
How to solve Minimum Height Trees
Minimum Height Trees is a Topological Sort problem, part of Graph Traversal Patterns (DFS & BFS). Master topological sorting using Kahn's BFS algorithm. Solve course schedule and build order problems.
Work towards the solution in these steps:
- How many MHTs can a graph have at most?
The reference solution runs in O(n) time and O(n) space.
The Minimum Height Trees solution and editorial walks through the full approach with reference code.
Problem statement
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.
Topics and companies
Topics: Depth-First Search, Breadth-First Search, Graph, Topological Sort.
Reported in interviews at Facebook.
How to practise Minimum Height Trees on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.
Open Minimum Height Trees in the code editor, or read the Minimum Height Trees editorial for a worked solution with its approach and complexity analysis.
Where Minimum Height Trees sits in the DSA pattern sheet
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Graph BFS - Topological Sort (Kahn's Algorithm) subpattern
- The full DSA patterns sheet
Problems related to Minimum Height Trees
Other problems that use the same Graph BFS - Topological Sort (Kahn's Algorithm) and Graph Traversal Patterns (DFS & BFS) techniques:
- Alien Dictionary — Hard, same subpattern
- Build a Matrix With Conditions — Hard, same subpattern
- Course Schedule IV — Medium, same subpattern
- Find All Possible Recipes from Given Supplies — Medium, same subpattern
- Largest Color Value in a Directed Graph — Hard, same subpattern
- Parallel Courses — Medium, same subpattern
Minimum Height Trees FAQ
What is the LeetCode number of Minimum Height Trees?
Minimum Height Trees is LeetCode problem 310, rated Medium.
What pattern is used to solve Minimum Height Trees?
Minimum Height Trees is a Topological Sort problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph BFS - Topological Sort (Kahn's Algorithm) subpattern.
What is the time complexity of Minimum Height Trees?
The reference solution runs in O(n) time and O(n) space.
Which companies ask Minimum Height Trees?
Minimum Height Trees has been reported in interviews at Facebook.