Minimum Height Trees

Minimum Height Trees 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.

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), where n is the number of nodes. Each edge and node is processed at most once during the leaf trimming process. time and O(n), for the adjacency list and auxiliary data structures (leaves, etc). 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

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:

Preparing this workspace.