We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Height Trees

Difficulty: Medium

Problem Description

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges, return a list of all Minimum Height Trees (MHTs) root labels. A tree is a connected graph without cycles, and the height of a tree is defined as the number of edges on the longest downward path between the root and a leaf.

Key Insights

  • A tree with n nodes has exactly n - 1 edges.
  • Minimum Height Trees can be found by identifying the centroids of the tree, which minimize the height when chosen as roots.
  • The centroids can be efficiently determined using a multi-phase pruning technique where leaves are removed iteratively until the remaining nodes are the centroids.
  • The height of the tree is minimized when the root is positioned centrally in relation to all other nodes.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The solution uses a Breadth-First Search (BFS) approach to find the Minimum Height Trees. The algorithm works as follows:

  1. Construct an adjacency list from the given edges to represent the tree.
  2. Identify all the leaf nodes (nodes with only one edge).
  3. Iteratively remove these leaves from the tree until only one or two nodes remain.
  4. The remaining nodes are the roots of the Minimum Height Trees.

This approach ensures that we efficiently find the centroids of the tree, which result in the minimum height when selected as roots.

Code Solutions

from collections import defaultdict, deque

def findMinHeightTrees(n, edges):
    if n == 1:
        return [0]
    
    # Build the adjacency list
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # Initialize the first layer of leaves
    leaves = [i for i in range(n) if len(graph[i]) == 1]
    
    # Trim the leaves until reaching the centroids
    while n > 2:
        n -= len(leaves)
        new_leaves = []
        for leaf in leaves:
            neighbor = graph[leaf].pop()  # The only neighbor
            graph[neighbor].remove(leaf)   # Remove the leaf from the neighbor
            if len(graph[neighbor]) == 1:  # If the neighbor has become a leaf
                new_leaves.append(neighbor)
        leaves = new_leaves
    
    return leaves
← Back to All Questions