LeetCode 310: Minimum Height Trees Solution in Python – A Step-by-Step Guide

What Is LeetCode 310: Minimum Height Trees?

In LeetCode 310: Minimum Height Trees, you’re given an undirected graph with n nodes (labeled 0 to n-1) and a list of edges, representing a tree (no cycles). Your task is to find all nodes that, when chosen as the root, result in a tree with the minimum possible height—where height is the longest path from root to leaf. For example, in a tree with edges [[1,0],[1,2],[1,3]], nodes 1 has a height of 1, making it a minimum height root. This problem tests your ability to analyze tree structures and optimize their depth.

Problem Statement

• Input: Integer n (number of nodes) and edges (list of [u, v] pairs representing undirected edges).
• Output: A list of integers—all nodes that yield the minimum height when rooted.
• Rules:
• Graph is a tree (connected, no cycles).
• Edges are undirected.

Constraints

• 1 <= n <= 2 * 10⁴
• edges.length == n - 1
• 0 <= u, v < n, u != v
• Graph has no cycles.

Examples

• Input: n = 4, edges = [[1,0],[1,2],[1,3]]
• Output: [1] (Root at 1 gives height 1)
• Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
• Output: [3, 4] (Roots at 3 or 4 give height 2)
• Input: n = 1, edges = []
• Output: [0]

Understanding the Problem: Finding Central Nodes

To solve LeetCode 310: Minimum Height Trees in Python, we need to identify nodes that minimize the tree’s height when rooted there. A brute-force approach might root the tree at each node and compute heights, but that’s O(n²)—too slow. Instead, we’ll use:

• Best Solution (Leaf Trimming): O(n) time, O(n) space—peels away leaves to find the center.
• Alternative Solution (BFS from Each Node): O(n²) time, O(n) space—checks all possibilities.

Let’s start with the leaf-trimming solution, explained in a beginner-friendly way.

Best Solution: Leaf Trimming (Topological Sort)

Why This Is the Best Solution

The leaf-trimming approach is the top choice for LeetCode 310 because it’s efficient—O(n) time, O(n) space—and leverages the tree’s structure brilliantly. It works like peeling an onion: remove all leaves (nodes with degree 1), update the graph, and repeat until only the central nodes remain. These are the minimum height roots because they’re the “middle” of the tree, minimizing the longest path. It’s like finding the heart of the network—fast and elegant!

How It Works

Think of the tree as a network you’re simplifying:

• Step 1: Build Adjacency List:
• Create a graph representation and track node degrees.
• Step 2: Identify Leaves:
• Find nodes with degree 1 (connected to only one neighbor).
• Step 3: Trim Leaves:
• Remove leaves, decrease neighbors’ degrees, and repeat.
• Step 4: Stop at Core:
• When 1 or 2 nodes remain, they’re the minimum height roots.
• Step 5: Why It Works:
• In a tree, the centroid (1 or 2 nodes) balances the height.
• Trimming leaves converges to this centroid.

It’s like pruning a tree to reveal its center!

Step-by-Step Example

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

• Graph: 0-3-1, 2-3, 3-4-5
• Degrees: [1, 1, 1, 4, 2, 1]
• Round 1: Leaves = [0, 1, 2, 5]
• Remove 0, 1, 2: 3’s degree → 1
• Remove 5: 4’s degree → 1
• Remaining: [3, 4], degrees [1, 1]
• Round 2: Leaves = [3, 4]
• Remove both, no nodes left.
• Result: Stop at [3, 4]—height 2 from either.

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]

        # Build adjacency list and degrees
        graph = [set() for _ in range(n)]
        degrees = [0] * n
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)
            degrees[u] += 1
            degrees[v] += 1

        # Find initial leaves
        leaves = [i for i in range(n) if degrees[i] == 1]

        # Trim leaves until 2 or fewer nodes remain
        remaining = n
        while remaining > 2:
            remaining -= len(leaves)
            new_leaves = []
            for leaf in leaves:
                # Update neighbor
                for neighbor in graph[leaf]:
                    graph[neighbor].remove(leaf)
                    degrees[neighbor] -= 1
                    if degrees[neighbor] == 1:
                        new_leaves.append(neighbor)
                graph[leaf].clear()
            leaves = new_leaves

        # Remaining nodes are the result
        return [i for i in range(n) if degrees[i] > 0 or degrees[i] == 1]

• Lines 3-4: Edge case—single node.
• Lines 6-12: Build graph and degrees.
• Line 14: Start with leaves (degree 1).
• Lines 17-25: Trim loop:
• Reduce count, process each leaf.
• Update neighbors, find new leaves.
• Line 27: Return remaining nodes.
• Time Complexity: O(n)—each node processed once.
• Space Complexity: O(n)—graph storage.

This is like a tree-pruning masterclass—quick and precise!

Alternative Solution: BFS from Each Node

Why an Alternative Approach?

The BFS (Breadth-First Search) approach computes the height from each node as root—O(n²) time, O(n) space. It’s more straightforward but slower, making it a good learning tool to understand tree heights explicitly. It’s like exploring every possibility—thorough but exhaustive!

How It Works

Run BFS from each node:

• Step 1: Build adjacency list.
• Step 2: For each node:
• Use BFS to find max distance (height).
• Step 3: Track nodes with minimum height.

Step-by-Step Example

Example: n = 4, edges = [[1,0],[1,2],[1,3]]

• Root 0: Height = 2 (0-1-2/3).
• Root 1: Height = 1 (1-0/2/3).
• Root 2: Height = 2.
• Root 3: Height = 2.
• Result: [1] (min height 1).

Code for BFS Approach

Copy codefrom collections import deque

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]

        # Build adjacency list
        graph = [set() for _ in range(n)]
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)

        # BFS to get height from root
        def bfs(root):
            visited = [False] * n
            queue = deque([root])
            visited[root] = True
            height = -1
            while queue:
                height += 1
                for _ in range(len(queue)):
                    node = queue.popleft()
                    for neighbor in graph[node]:
                        if not visited[neighbor]:
                            visited[neighbor] = True
                            queue.append(neighbor)
            return height

        # Find height for each root
        heights = [bfs(i) for i in range(n)]
        min_height = min(heights)
        return [i for i in range(n) if heights[i] == min_height]

• Time Complexity: O(n²)—BFS for each node.
• Space Complexity: O(n)—graph and queue.

It’s a full tree explorer!

Comparing the Two Solutions

• Leaf Trimming (Best):
• Pros: O(n) time, O(n) space, fast.
• Cons: Less intuitive initially.
• BFS (Alternative):
• Pros: O(n²) time, O(n) space, clear logic.
• Cons: Much slower.

Leaf trimming wins big.

Additional Examples and Edge Cases

• n=2, [[0,1]]: [0, 1].
• n=3, [[0,1],[1,2]]: [1].
• n=1, []: [0].

Both handle these well.

Complexity Breakdown

• Leaf Trimming: Time O(n), Space O(n).
• BFS: Time O(n²), Space O(n).

Trimming is optimal.

Key Takeaways

• Leaf Trimming: Peel to the core—brilliant!
• BFS: Explore all—educational!
• Python: Sets and lists shine—see [Python Basics](/python/basics).
• Trees: Centroids are key.

Final Thoughts: Find the Tree’s Heart

LeetCode 310: Minimum Height Trees in Python is a graph theory gem. Leaf trimming offers speed and elegance, while BFS provides a clear baseline. Want more tree challenges? Try LeetCode 104: Maximum Depth of Binary Tree or LeetCode 543: Diameter of Binary Tree. Ready to trim? Head to Solve LeetCode 310 on LeetCode and find those central nodes today!