NUHMAN.com

Introduction

LeetCode 310: Minimum Height Trees (MHT) requires us to find the nodes that minimize the height of a tree when rooted at those nodes. Specifically, given an undirected graph where nodes represent cities and edges represent roads, we need to determine the nodes (or cities) that, if chosen as the root, result in the smallest possible height (or maximum distance from the root to any leaf node). This problem can be modeled as a graph problem, and the solution involves finding the center of the tree.

Problem Statement

You are given a graph with n nodes labeled from 0 to n - 1 and an array edges of length n - 1, where each edge is represented as a pair [u, v] that connects nodes u and v in an undirected tree.

Return a list of all nodes that can be the root of a minimum height tree.

Note: The height of a tree is the number of edges on the longest path from the root to any leaf.

Example

python

# Example 1
Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]
Output: [1]
Explanation: The tree looks like:
     0
     |
     1
   /   \
  2     3
The height of the tree is 2, and node 1 is the center of the tree.

# Example 2
Input: n = 6, edges = [[3, 0], [3, 1], [3, 2], [3, 4], [5, 4]]
Output: [3, 4]
Explanation: The tree looks like:
        0
        |
     1--3--2
        |
        4
        |
        5
The height of the tree is 3, and nodes 3 and 4 are the centers of the tree.

Step-by-Step Solution

🧠 Intuition

The key observation in solving this problem is that the center of a tree, which results in the minimum height when rooted, lies at the center of its longest path (or diameter). To find the center:

1. Trim leaves of the tree iteratively until we are left with 1 or 2 nodes, which represent the center of the tree.
2. These nodes will be the roots that minimize the height of the tree.

✅ Approach

1. Remove leaves (nodes with a single neighbor) layer by layer. Each time we remove the leaves, we reduce the diameter of the tree.
2. Continue this process until only 1 or 2 nodes are left. These nodes will be the centers of the tree, and the tree rooted at these nodes will have the minimum height.

This method can be implemented efficiently using Breadth-First Search (BFS).

Detailed Steps:

1. Initialize a queue and add all leaves (nodes with only one neighbor) to it.
2. Iteratively remove the leaves from the graph:

• For each leaf, remove it and decrement the degree of its neighboring node.
• If a neighboring node becomes a leaf, add it to the queue.

1. Repeat this process until the number of nodes remaining is 1 or 2. These remaining nodes will be the roots that minimize the tree's height.

✅ Python Code

python

from collections import deque

class Solution:
    def findMinHeightTrees(self, n: int, edges: list[list[int]]) -> list[int]:
        if n == 1:
            return [0]
        
        # Build the graph
        graph = {i: [] for i in range(n)}
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        # Initialize leaves
        leaves = deque([i for i in range(n) if len(graph[i]) == 1])
        
        # Trim leaves until we are left with the center(s)
        while n > 2:
            size = len(leaves)
            n -= size  # Removing leaves
            for _ in range(size):
                leaf = leaves.popleft()
                # Remove leaf from its neighbor
                for neighbor in graph[leaf]:
                    graph[neighbor].remove(leaf)
                    if len(graph[neighbor]) == 1:  # If it becomes a leaf
                        leaves.append(neighbor)
        
        # Remaining nodes are the centers of the tree
        return list(leaves)

Explanation of the Code

1. Base Case (n == 1):

• If there's only one node, it is trivially the center of the tree, so we return [0].

1. Graph Construction:

• We build the graph using an adjacency list. For each edge, we add both directions (u -> v and v -> u).

1. Identify Leaves:

• Leaves are nodes with only one neighbor. We initialize a queue to keep track of all leaves.

1. Trim Leaves Iteratively:

• We process each leaf by removing it and updating the degree of its neighbor. If a neighbor becomes a leaf (i.e., it now has only one neighbor), we add it to the queue.
• This process continues until only 1 or 2 nodes remain.

1. Return the Centers:

• The remaining nodes in the queue (leaves) after all trimming are the centers of the tree.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(n)Space ComplexityO(n)

• Time Complexity: We process each node and edge exactly once, so the time complexity is O(n), where n is the number of nodes.
• Space Complexity: The space complexity is O(n) because we store the graph and the leaves queue.

🔍 Edge Cases

1. Single Node (n == 1):

• If the graph has only one node, the answer is [0] as it's the only possible root.

1. Linear Tree:

• If the tree is a straight line (i.e., a path), the center will be the middle node or nodes.

1. All Nodes Forming a Star:

• If all nodes are connected to a central node (like a star), the center of the tree is the central node.

✅ Conclusion

LeetCode 310: Minimum Height Trees requires finding the center nodes that minimize the height of the tree. This can be achieved by iteratively removing leaves until 1 or 2 nodes remain, which are the centers of the tree. The solution uses a breadth-first approach to efficiently compute the result in O(n) time.