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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Height Trees

Number: 310

Difficulty: Medium

Paid? No

Companies: Splunk, Google, Meta, Microsoft, Citadel, Amazon, Adobe

Problem Description

Given a tree with n nodes labeled from 0 to n - 1 and an array of n - 1 edges, the goal is to find all the roots of Minimum Height Trees (MHTs). A minimum height tree is defined as a rooted tree whose height (the number of edges on the longest downward path from the root to a leaf) is minimized. You can choose any node as the root, and your task is to return all nodes that can serve as roots for the MHTs.

Key Insights

  • A tree can have at most two centers that will serve as the roots for its minimum height trees.
  • Instead of trying all possible roots, we can remove leaves layer by layer until we are left with the central node(s).
  • The process is similar to a topological sort on the tree.
  • When there are 2 or fewer nodes left, these nodes are the centers (roots) of MHTs.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes, since we process each node and edge once.
Space Complexity: O(n) for storing the graph and additional data structures like the leaves list.

Solution

The solution builds an undirected graph from the input, then identifies and removes node-leaves iteratively. A leaf is defined as a node connected to only one other node. By repeatedly removing the leaves and updating the graph (decreasing neighbor degrees), the algorithm peels away the outer layers of the tree. When only one or two nodes remain, these nodes are the centers of the tree and form the roots of the minimum height trees.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        # Special case: if there's only one node, return it as the only MHT root.
        if n == 1:
            return [0]
        
        # Build the graph using an adjacency list with sets for neighbors.
        graph = [set() for _ in range(n)]
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)
        
        # Initialize the first layer of leaves (nodes with one neighbor).
        leaves = [i for i in range(n) if len(graph[i]) == 1]
        
        # Remove leaves layer by layer until at most 2 nodes remain.
        remaining_nodes = n
        while remaining_nodes > 2:
            remaining_nodes -= len(leaves)
            new_leaves = []
            # Remove current leaves.
            for leaf in leaves:
                # Since it's a leaf, there is only one neighbor.
                neighbor = graph[leaf].pop()
                # Remove the connection from the neighbor to the leaf.
                graph[neighbor].remove(leaf)
                # If the neighbor becomes a leaf, add it to the new leaves list.
                if len(graph[neighbor]) == 1:
                    new_leaves.append(neighbor)
            leaves = new_leaves
        
        # The remaining nodes are the roots of the MHTs.
        return leaves
← Back to All Questions