Minimum Height Trees

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] = [a_i, b_i] indicates that there is an undirected edge between the two nodes a_i and b_i 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.

For example:

If n = 4, edges = [[1,0],[1,2],[1,3]], the output is [1]. As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

If n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]], the output is [3,4].

## Minimum Height Trees

This problem asks us to find the root nodes of minimum height trees (MHTs) given a tree represented by `n` nodes and `n-1` edges. A minimum height tree is a rooted tree with the smallest possible height among all possible rooted trees.

### Brute Force Approach

A naive approach would be to try each node as the root, calculate the height of the tree rooted at that node, and then find the nodes that result in the minimum height. This involves a Breadth-First Search (BFS) or Depth-First Search (DFS) for each node to compute the height.

```python
def find_min_height_trees_brute_force(n, edges):
    if n <= 0:
        return []
    if n == 1:
        return [0]

    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    def get_height(root):
        q = [(root, 0)]
        visited = {root}
        max_height = 0
        while q:
            node, height = q.pop(0)
            max_height = max(max_height, height)
            for neighbor in adj[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    q.append((neighbor, height + 1))
        return max_height

    min_height = float('inf')
    roots = []
    for i in range(n):
        height = get_height(i)
        if height < min_height:
            min_height = height
            roots = [i]
        elif height == min_height:
            roots.append(i)
    return roots

Complexity Analysis:

• Time Complexity: O(n^2) because, for each of the n nodes, we perform a BFS/DFS which takes O(n) time.
• Space Complexity: O(n) to store the adjacency list and the queue for BFS/DFS.

Optimal Approach (Topological Sort)

The optimal solution uses a topological sort-like approach. The main idea is to iteratively remove leaf nodes from the graph until only the central node(s) remain. These central nodes are the roots of the minimum height trees.

1. Build the adjacency list for the graph.
2. Find all leaf nodes (nodes with only one neighbor).
3. Iteratively remove the leaf nodes. Each time a leaf node is removed, check if any of its neighbors have become leaf nodes.
4. Repeat until there are only 1 or 2 nodes left. These are the root nodes of the MHTs.

from collections import deque

def find_min_height_trees(n, edges):
    if n <= 0:
        return []
    if n == 1:
        return [0]

    adj = [set() for _ in range(n)]
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)

    leaves = deque()
    for i in range(n):
        if len(adj[i]) == 1:
            leaves.append(i)

    remaining_nodes = n
    while remaining_nodes > 2:
        num_leaves = len(leaves)
        remaining_nodes -= num_leaves

        for _ in range(num_leaves):
            leaf = leaves.popleft()
            neighbor = adj[leaf].pop()
            adj[neighbor].remove(leaf)
            if len(adj[neighbor]) == 1:
                leaves.append(neighbor)

    return list(leaves)

Example:

For the input n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]

1. Adjacency List:

   0: [3]
   1: [3]
   2: [3]
   3: [0, 1, 2, 4]
   4: [3, 5]
   5: [4]
   

2. Initial Leaves: [0, 1, 2, 5]
3. Iteration 1: Remove [0, 1, 2, 5]. Remaining nodes: 2. New leaves: [3, 4]
4. Result: [3, 4]

Big(O) Runtime Analysis

• Time Complexity: O(n), where n is the number of nodes. Building the adjacency list takes O(n). The topological sort-like approach processes each node at most once when it's a leaf, and the number of edges is n-1, so the overall time complexity is O(n).

Big(O) Space Usage Analysis

• Space Complexity: O(n) to store the adjacency list. In the worst-case scenario (e.g., a star graph), a node can have n-1 neighbors. The leaves queue also takes O(n) space in the worst case.

Edge Cases and Considerations

1. Empty Graph (n = 0): Return an empty list because there are no nodes.
2. Single Node Graph (n = 1): Return [0] as the only node is also the root.
3. Disconnected Graph: The problem statement guarantees that the input is a tree, meaning it's connected. But if it weren't, you'd need to apply the above topological sort approach to each connected component.
4. Duplicate Edges: The problem states there are no repeated edges, so we don't need to handle this.
5. Invalid Node Numbers: The problem states nodes are labeled from 0 to n-1. If this wasn't guaranteed, we'd need to validate the node numbers.