Minimum Height Trees

Introduction

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.)

Solutions

1. "Trim the Leaves"

Edge Case Handling: If n is 1, the tree consists of a single node, which is trivially the root of the MHT. In this case, simply return the single node.
Trimming Leaves: Begin by identifying all leaf nodes (nodes with only one connection). Iteratively remove these leaf nodes from the tree. As leaves are removed, update their neighboring nodes to reflect the loss of a connection. If a neighboring node becomes a leaf after removing a leaf, it is added to the new list of leaves.
Remaining Nodes: Continue this process of trimming leaves layer by layer until only one or two nodes remain. These remaining nodes are the roots of the MHTs, as they are centrally located, minimizing the maximum distance to any other node in the tree.

main.py

from collections import defaultdict
from typing import List


def minimum_height_trees(n: int, edges: List[List[int]]) -> List[int]:
    if n == 1:
        return [0]
    
    # Build the graph
    graph = defaultdict(list)
    for source, dest in edges:
        graph[source].append(dest)
        graph[dest].append(source)
    
    # Initialize the first layer of leaves
    leaves = [i for i in range(n) if len(graph[i]) == 1]
    
    remaining_nodes = n
    while remaining_nodes > 2:
        remaining_nodes -= len(leaves)
        new_leaves = []
        
        # Remove the current leaves along with the edges
        for leaf in leaves:
            neighbor = graph[leaf].pop()
            graph[neighbor].remove(leaf)
            
            # If the neighbor has become a leaf, add it to the new leaves
            if len(graph[neighbor]) == 1:
                new_leaves.append(neighbor)
        
        leaves = new_leaves
    
    # The remaining nodes are the roots of MHTs
    return leaves

Introduction

Solutions

1. "Trim the Leaves"

References