#310

Medium

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Minimum Height Trees

Identify all roots of a tree that produce minimum height using graph indegree analysis and topological trimming.

depth first search breadth first search graph topological sort

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.

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.

terminal

Solution

Solution 1: Topological Sorting

If the tree only has one node, then this node is the root of the minimum height tree. We can directly return this node.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]
        g = [[] for _ in range(n)]
        degree = [0] * n
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
            degree[a] += 1
            degree[b] += 1
        q = deque(i for i in range(n) if degree[i] == 1)
        ans = []
        while q:
            ans.clear()
            for _ in range(len(q)):
                a = q.popleft()
                ans.append(a)
                for b in g[a]:
                    degree[b] -= 1
                    if degree[b] == 1:
                        q.append(b)
        return ans

Continue Practicing

#329 longest increasing path in a matrix #210 course schedule ii #207 course schedule