LeetCode 310 - Minimum Height Trees

This problem gives us an undirected tree with n nodes labeled from 0 to n - 1. The input edges describes the connections between nodes, and because the graph is guaranteed to be a tree, several important properties immediately hold true.

leetcodemediumdepth-first-searchbreadth-first-searchgraph-theorytopological-sort

LeetCode Problem 310

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

Solution

Problem Understanding

This problem gives us an undirected tree with n nodes labeled from 0 to n - 1. The input edges describes the connections between nodes, and because the graph is guaranteed to be a tree, several important properties immediately hold true.

A tree with n nodes always has exactly n - 1 edges, and there is exactly one path between any pair of nodes. This means the graph is connected and contains no cycles.

The task is to determine which node or nodes can be chosen as the root such that the resulting rooted tree has the minimum possible height.

The height of a rooted tree is defined as the number of edges on the longest downward path from the root to any leaf node. Different choices of root can produce very different heights.

For example, consider a star-shaped tree:

    0
    |
2 - 1 - 3

If node 1 is the root, the height is 1, because every other node is directly connected to it. If instead node 0 is the root, the height becomes 2.

The problem asks us to return all nodes that produce the minimum possible height.

The constraints are important:

  • 1 <= n <= 2 * 10^4
  • The graph is guaranteed to be a valid tree

The upper bound of 20,000 nodes means inefficient repeated traversals can become too slow. Any algorithm significantly worse than O(n) or O(n log n) may struggle.

There are several important edge cases:

  • A tree with only one node
  • A tree with two nodes
  • A line-shaped tree, where the middle node or middle two nodes become the answer
  • A star-shaped tree, where the center node is the answer

The guarantee that the input is always a tree simplifies the problem because we never need to handle disconnected graphs or cycles.

Approaches

Brute Force Approach

The brute force solution tries every node as the root.

For each node:

  1. Run either BFS or DFS to compute the maximum depth from that node
  2. Treat that maximum depth as the tree height
  3. Keep track of the minimum height encountered
  4. Return all nodes that achieve that minimum

This works because we directly evaluate the definition of the problem. Every possible root is tested, and the exact height is computed.

However, this is too slow for the constraints.

If we perform a BFS or DFS from every node:

  • Each traversal costs O(n)
  • We repeat this for all n nodes

This results in O(n^2) time complexity.

With n = 20,000, this becomes approximately 400 million operations in the worst case, which is too expensive.

Optimal Approach, Topological Leaf Trimming

The key insight is that minimum height tree roots are always located near the center of the tree.

Think about repeatedly removing all leaf nodes:

  • Leaves are nodes with only one connection
  • Removing outer layers gradually shrinks the tree inward
  • Eventually, only the central node or two central nodes remain

These remaining nodes are exactly the roots of the minimum height trees.

This process is very similar to topological sorting using indegrees:

  • Leaves have degree 1
  • We repeatedly remove current leaves
  • Their neighbors may become new leaves
  • Continue until at most two nodes remain

Why at most two?

A tree can have:

  • One center node
  • Two center nodes

This corresponds to whether the tree diameter has odd or even length.

Because every edge and node is processed only once, this solution runs in linear time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Run BFS/DFS from every node to compute height
Optimal O(n) O(n) Repeatedly trim leaves until tree centers remain

Algorithm Walkthrough

  1. Handle the single-node edge case.

If n == 1, there are no edges and the only possible root is node 0. Return [0]. 2. Build the adjacency list.

Since the graph is undirected, each edge [u, v] is added to both adjacency lists.

We also maintain a degree array where degree[i] stores how many neighbors node i currently has. 3. Identify all initial leaves.

A leaf is any node whose degree equals 1.

We place all leaves into a queue because they form the outermost layer of the tree. 4. Repeatedly remove leaves layer by layer.

At each iteration:

  • Count how many leaves currently exist
  • Remove them from the tree
  • Decrease the degree of their neighbors
  • If a neighbor becomes degree 1, it becomes a new leaf

This simulates peeling the tree from the outside inward. 5. Stop when at most two nodes remain.

The remaining nodes are the centers of the tree.

These centers are guaranteed to produce minimum height trees.

Why it works

The algorithm works because the height of a rooted tree depends on the maximum distance to any leaf. Nodes near the outside naturally produce larger heights because paths to opposite sides become longer.

By repeatedly removing leaves, we eliminate nodes that cannot possibly be optimal roots. The process converges toward the geometric center of the tree.

A tree can only have one or two centers, and these centers minimize the maximum distance to all other nodes. Therefore, the final remaining nodes are exactly the roots of all minimum height trees.

Python Solution

from collections import deque
from typing import List

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

        graph = [[] for _ in range(n)]
        degree = [0] * n

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

            degree[u] += 1
            degree[v] += 1

        leaves = deque()

        for node in range(n):
            if degree[node] == 1:
                leaves.append(node)

        remaining_nodes = n

        while remaining_nodes > 2:
            leaf_count = len(leaves)
            remaining_nodes -= leaf_count

            for _ in range(leaf_count):
                leaf = leaves.popleft()

                for neighbor in graph[leaf]:
                    degree[neighbor] -= 1

                    if degree[neighbor] == 1:
                        leaves.append(neighbor)

        return list(leaves)

The implementation begins by handling the special case where the tree contains only one node. Since there are no edges, node 0 must be the answer.

Next, the adjacency list and degree array are constructed. The adjacency list allows efficient neighbor traversal, while the degree array tracks how many active connections each node currently has.

The queue stores all current leaves. Using a queue is appropriate because we process leaves level by level, similar to BFS.

The variable remaining_nodes tracks how many nodes are still part of the active tree. Each iteration removes one entire outer layer.

For every removed leaf, we decrement the degree of its neighbors. When a neighbor's degree becomes 1, it has become a new leaf and is added to the queue.

The process stops once only one or two nodes remain. These nodes are returned as the answer.

Go Solution

func findMinHeightTrees(n int, edges [][]int) []int {
	if n == 1 {
		return []int{0}
	}

	graph := make([][]int, n)
	degree := make([]int, n)

	for _, edge := range edges {
		u := edge[0]
		v := edge[1]

		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)

		degree[u]++
		degree[v]++
	}

	queue := []int{}

	for i := 0; i < n; i++ {
		if degree[i] == 1 {
			queue = append(queue, i)
		}
	}

	remainingNodes := n

	for remainingNodes > 2 {
		leafCount := len(queue)
		remainingNodes -= leafCount

		nextQueue := []int{}

		for _, leaf := range queue {
			for _, neighbor := range graph[leaf] {
				degree[neighbor]--

				if degree[neighbor] == 1 {
					nextQueue = append(nextQueue, neighbor)
				}
			}
		}

		queue = nextQueue
	}

	return queue
}

The Go implementation follows the same logic as the Python solution but uses slices instead of Python lists and deques.

Instead of using a queue structure from a library, the implementation processes slices level by level by building a nextQueue for the next iteration.

Go slices naturally handle dynamic resizing, making them suitable for adjacency lists and BFS layers.

There are no integer overflow concerns because node counts remain within standard integer limits.

Worked Examples

Example 1

Input:

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

Step 1: Build Graph

Node Neighbors Degree
0 [1] 1
1 [0,2,3] 3
2 [1] 1
3 [1] 1

Initial leaves:

[0, 2, 3]

Remaining nodes:

4

Step 2: Remove First Layer

Remove leaves 0, 2, and 3.

After updating degrees:

Node Updated Degree
1 0

Node 1 becomes the center.

Remaining nodes:

1

Stop because remaining_nodes <= 2.

Answer:

[1]

Example 2

Input:

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

Step 1: Build Graph

Node Neighbors Degree
0 [3] 1
1 [3] 1
2 [3] 1
3 [0,1,2,4] 4
4 [3,5] 2
5 [4] 1

Initial leaves:

[0, 1, 2, 5]

Remaining nodes:

6

Step 2: Remove First Layer

Remove leaves 0, 1, 2, 5.

Updated degrees:

Node Updated Degree
3 1
4 1

New leaves:

[3, 4]

Remaining nodes:

2

Stop because remaining_nodes <= 2.

Answer:

[3, 4]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node and edge is processed at most once
Space O(n) Adjacency list, degree array, and queue all require linear space

The algorithm is linear because each node enters and leaves the queue exactly once. Similarly, every edge is examined only when processing neighboring nodes during leaf removal.

This efficiency makes the solution suitable for the constraint limit of 20,000 nodes.

Test Cases

from typing import List
from collections import deque

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

        graph = [[] for _ in range(n)]
        degree = [0] * n

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

            degree[u] += 1
            degree[v] += 1

        leaves = deque()

        for node in range(n):
            if degree[node] == 1:
                leaves.append(node)

        remaining_nodes = n

        while remaining_nodes > 2:
            leaf_count = len(leaves)
            remaining_nodes -= leaf_count

            for _ in range(leaf_count):
                leaf = leaves.popleft()

                for neighbor in graph[leaf]:
                    degree[neighbor] -= 1

                    if degree[neighbor] == 1:
                        leaves.append(neighbor)

        return list(leaves)

solution = Solution()

assert solution.findMinHeightTrees(1, []) == [0]  # Single node tree

assert sorted(solution.findMinHeightTrees(
    4,
    [[1, 0], [1, 2], [1, 3]]
)) == [1]  # Star-shaped tree

assert sorted(solution.findMinHeightTrees(
    6,
    [[3, 0], [3, 1], [3, 2], [3, 4], [5, 4]]
)) == [3, 4]  # Two-center tree

assert sorted(solution.findMinHeightTrees(
    2,
    [[0, 1]]
)) == [0, 1]  # Two-node tree

assert sorted(solution.findMinHeightTrees(
    5,
    [[0, 1], [1, 2], [2, 3], [3, 4]]
)) == [2]  # Odd-length chain

assert sorted(solution.findMinHeightTrees(
    6,
    [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]]
)) == [2, 3]  # Even-length chain

assert sorted(solution.findMinHeightTrees(
    7,
    [[0, 1], [0, 2], [0, 3], [3, 4], [4, 5], [4, 6]]
)) == [3]  # Unbalanced tree

assert sorted(solution.findMinHeightTrees(
    3,
    [[0, 1], [1, 2]]
)) == [1]  # Small linear tree

Test Summary

Test Why
n = 1 Validates single-node edge case
Star-shaped tree Ensures center node is detected
Two-center example Confirms algorithm handles dual centers
Two-node tree Verifies both nodes are valid roots
Odd-length chain Tests single middle node
Even-length chain Tests two middle nodes
Unbalanced tree Validates trimming logic on irregular structures
Small linear tree Confirms basic path handling

Edge Cases

Single Node Tree

When n = 1, there are no edges and only one possible root exists.

This case is important because the normal leaf-trimming logic assumes at least one edge and at least one leaf with degree 1. In a single-node tree, the degree is 0.

Without explicit handling, the algorithm could incorrectly return an empty result.

The implementation correctly handles this case immediately:

if n == 1:
    return [0]

Two Node Tree

A tree with two connected nodes has two valid minimum height roots.

Example:

0 - 1

Rooting at either node produces height 1.

This case is tricky because both nodes are leaves from the start. The algorithm correctly returns both because the trimming process stops once remaining_nodes <= 2.

Long Linear Chain

Consider:

0 - 1 - 2 - 3 - 4

Naive implementations may incorrectly favor one side if the trimming logic is not symmetric.

The repeated leaf-removal process naturally converges toward the center:

[0,4] -> [1,3] -> [2]

This guarantees the middle node is returned.

For even-length chains, two middle nodes remain, which is also handled correctly by the stopping condition.