Skip to main content

Minimum Height Trees

Question​

What is the minimum number of edges needed to form a tree with a given height?

Example 1
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3, 4]

Solution​

all//Minimum Height Trees.py


from collections import defaultdict

def findMinHeightTrees(n, edges):
    if n == 1:
        return [0]
    adj = defaultdict(list)
    for i, j in edges:
        adj[i].append(j)
        adj[j].append(i)

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

    # remove leaf nodes until only one or two nodes remain
    while n > 2:
        n -= len(leaves)
        newLeaves = []
        for i in leaves:
            j = adj[i].pop()
            adj[j].remove(i)
            if len(adj[j]) == 1:
                newLeaves.append(j)
        leaves = newLeaves
    return leaves