Problem Description

You're given a tree with n nodes labeled from 0 to n - 1. The tree is represented as an undirected graph where any two nodes are connected by exactly one path (no cycles exist).

The tree is defined by:

• n: the number of nodes
• edges: an array of n - 1 edges where each edges[i] = [ai, bi] represents an undirected edge between nodes ai and bi

Your task is to find which nodes, when chosen as the root, would create trees with minimum height. The height of a rooted tree is the number of edges on the longest path from the root down to any leaf node.

Key Points:

• You can choose any node as the root of the tree
• Different root choices result in trees of different heights
• You need to find all nodes that minimize this height
• Return all such nodes (there can be multiple valid answers)

Example Understanding: If you have a linear chain of nodes 0-1-2-3-4, choosing node 2 (the middle) as root gives height 2, while choosing node 0 (an end) as root gives height 4. The middle node(s) minimize the height.

Special Case:

• If n = 1, there's only one node, so return [0]

The solution uses a clever approach: it repeatedly removes leaf nodes (nodes with only one connection) layer by layer from the outside in. The last remaining nodes are the centers of the tree, which form the minimum height trees when used as roots. This works because the optimal roots are always in the "center" of the tree structure.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem explicitly states we have an undirected graph representing a tree with n nodes and n-1 edges.

Is it a tree?

• Yes: The problem clearly defines the input as a tree - an undirected graph where any two vertices are connected by exactly one path (no cycles).

DFS

• We arrive at DFS as the algorithm choice for tree problems.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this tree problem.

Why DFS is Applicable

While the provided solution actually uses BFS with topological sorting (a level-by-level approach), DFS is equally valid for this problem:

1. Tree Traversal: DFS can be used to traverse the tree and calculate heights from any potential root node.

2. Height Calculation: For each node as a potential root, DFS can compute the maximum depth (height) of the tree by recursively exploring all paths.

3. Finding Centers: DFS can help identify the tree's center(s) by:

   • Computing the eccentricity of each node (maximum distance to any other node)
   • Finding nodes with minimum eccentricity

The solution uses a clever optimization with BFS and topological sorting to avoid repeated DFS calls, but the core problem of finding minimum height trees can definitely be solved using DFS by:

• Running DFS from each node to find its height when used as root
• Keeping track of the minimum height found
• Returning all nodes that achieve this minimum height

Intuition

Think about what makes a tree have minimum height when rooted at a particular node. The key insight is that the center of the tree will minimize the maximum distance to all other nodes.

Imagine a tree as a physical object - if you want to minimize the furthest distance from a central point to any edge, you'd place that point at the center. Similarly, the root nodes that create minimum height trees are those at the "center" of the graph structure.

But how do we find the center? Consider this observation: leaf nodes can never be optimal roots (except in trivial cases). Why? Because a leaf node is at the "edge" of the tree - choosing it as root means all other nodes are on one side, maximizing the height.

This leads to a brilliant approach: peel away the leaves layer by layer, like peeling an onion.

Here's the key reasoning:

1. Start with all leaf nodes (nodes with degree 1)
2. Remove them simultaneously, which exposes a new layer of leaf nodes
3. Keep peeling until we can't peel anymore
4. What remains? The center node(s) of the tree!

Why does this work? Because we're symmetrically removing the outermost nodes from all directions. The last nodes to be removed are equidistant from all the furthest leaf nodes - these are our centers.

An important property: a tree can have at most 2 center nodes. If it has more than 2 nodes at the center, it would create a cycle, violating the tree property.

The algorithm essentially finds the nodes that would be visited last in a "reverse" BFS that starts from all leaves simultaneously and moves inward. These central nodes, when chosen as roots, balance the tree optimally, minimizing the maximum distance to any leaf.

Solution Approach

The implementation uses topological sorting with BFS to systematically peel off leaf nodes layer by layer until we reach the center(s) of the tree.

Data Structures Used:

1. Adjacency List (g): Store the graph representation where g[i] contains all neighbors of node i
2. Degree Array (degree): Track the number of connections for each node
3. Queue (deque): Store current layer of leaf nodes for BFS processing
4. Answer List (ans): Keep track of nodes in the current layer

Algorithm Steps:

1. Handle Edge Case:

   if n == 1:
       return [0]

   If there's only one node, it's automatically the root of the minimum height tree.

2. Build Graph Representation:

   g = [[] for _ in range(n)]
   degree = [0] * n
   for a, b in edges:
       g[a].append(b)
       g[b].append(a)
       degree[a] += 1
       degree[b] += 1

   Create an adjacency list and count the degree (number of connections) for each node.

3. Initialize Queue with Leaf Nodes:

   q = deque(i for i in range(n) if degree[i] == 1)

   Find all nodes with degree 1 (leaf nodes) and add them to the queue.

4. Layer-by-Layer Peeling:

   while q:
       ans.clear()
       for _ in range(len(q)):
           a = q.popleft()
           ans.append(a)
           for b in g[a]:
               degree[b] -= 1
               if degree[b] == 1:
                   q.append(b)

   • Process all nodes in the current layer (current leaves)
   • For each leaf, reduce the degree of its neighbors by 1
   • If a neighbor becomes a new leaf (degree becomes 1), add it to the queue for the next layer
   • Clear and update ans with each layer, so ans always contains the most recent layer processed

5. Return the Center Nodes: The last layer processed (remaining in ans) contains the center node(s) of the tree, which are the roots of minimum height trees.

Key Insight: By processing all leaves of each layer simultaneously, we ensure that we're moving inward symmetrically from all directions. The algorithm terminates when we've reached the center, leaving us with either 1 or 2 nodes (a tree can have at most 2 centers).

Time Complexity: O(n) - We visit each node and edge once Space Complexity: O(n) - For storing the graph and auxiliary data structures

Example Walkthrough

Let's walk through a concrete example to see how the algorithm finds minimum height trees.

Example Input:

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

This creates the following tree structure:

    1
    |
    0---2---4---5
        |
        3

Step 1: Build the graph and identify initial leaves

After building the adjacency list and calculating degrees:

• Node 0: neighbors = [1, 2], degree = 2
• Node 1: neighbors = [0], degree = 1 (leaf!)
• Node 2: neighbors = [0, 3, 4], degree = 3
• Node 3: neighbors = [2], degree = 1 (leaf!)
• Node 4: neighbors = [2, 5], degree = 2
• Node 5: neighbors = [4], degree = 1 (leaf!)

Initial queue: [1, 3, 5] (all nodes with degree 1)

Step 2: First layer peeling

Process nodes 1, 3, and 5:

• Remove node 1: Reduce degree of node 0 from 2 to 1 → Node 0 becomes a new leaf!
• Remove node 3: Reduce degree of node 2 from 3 to 2
• Remove node 5: Reduce degree of node 4 from 2 to 1 → Node 4 becomes a new leaf!

After first layer:

• ans = [1, 3, 5]
• New queue: [0, 4]
• Remaining nodes with their updated degrees: {0:1, 2:2, 4:1}

Step 3: Second layer peeling

Process nodes 0 and 4:

• Remove node 0: Reduce degree of node 2 from 2 to 1 → Node 2 becomes a new leaf!
• Remove node 4: Reduce degree of node 2 from 1 to 0

After second layer:

• ans = [0, 4]
• New queue: [2]
• Remaining node: {2:0}

Step 4: Final layer

Process node 2:

• Remove node 2: No more neighbors to update
• ans = [2]
• Queue becomes empty

Result: The algorithm returns [2] as the only node that creates a minimum height tree.

Verification: Let's verify by checking the heights when different nodes are chosen as root:

• Root at node 0: Height = 3 (path: 0→2→4→5)
• Root at node 1: Height = 4 (path: 1→0→2→4→5)
• Root at node 2: Height = 2 (paths: 2→0→1, 2→4→5, 2→3 all have max length 2)
• Root at node 3: Height = 3 (path: 3→2→4→5)
• Root at node 4: Height = 3 (path: 4→2→0→1)
• Root at node 5: Height = 4 (path: 5→4→2→0→1)

Node 2 indeed produces the minimum height of 2, confirming our algorithm's result!

The key insight is that by peeling leaves symmetrically from all directions, we naturally converge on the center node(s) that balance the tree optimally.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm processes each node and edge a constant number of times:

• Building the adjacency list takes O(n) time since we iterate through all edges once (there are n-1 edges in a tree)
• Computing initial degrees takes O(n) time
• The BFS-like traversal processes each node exactly once when it's removed from the queue, taking O(n) time total
• For each node removal, we update its neighbors' degrees, which across all iterations touches each edge twice (once from each endpoint), resulting in O(n) operations total

Space Complexity: O(n)

The algorithm uses several data structures that scale with the number of nodes:

• The adjacency list g stores all edges, requiring O(n) space (since a tree with n nodes has n-1 edges, and each edge is stored twice)
• The degree array stores one value per node, using O(n) space
• The queue q can contain at most O(n) nodes
• The ans list stores at most O(n) nodes (though in practice it will be at most 2 for the final result)

Common Pitfalls

1. Not Handling the Single Node Case

Pitfall: Forgetting to handle n = 1 as a special case causes the algorithm to fail since there are no edges and no leaves with degree 1.

Issue Example:

# Without the edge case check
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
    adjacency_list = [[] for _ in range(n)]
    node_degrees = [0] * n
    # When n=1 and edges=[], no nodes have degree 1
    leaves_queue = deque(node for node in range(n) if node_degrees[node] == 1)
    # Queue is empty, while loop never executes
    # Returns empty list instead of [0]

Solution: Always check for n == 1 at the beginning and return [0] immediately.

2. Incorrect Answer List Management

Pitfall: Not clearing the answer list at the start of each layer iteration, causing all processed nodes to accumulate instead of keeping only the last layer.

Issue Example:

remaining_nodes = []
while leaves_queue:
    # Forgetting to clear - accumulates all nodes ever processed
    # remaining_nodes.clear()  # Missing this line!
    for _ in range(len(leaves_queue)):
        leaf_node = leaves_queue.popleft()
        remaining_nodes.append(leaf_node)
        # ...
# Returns all nodes instead of just the center nodes

Solution: Always call remaining_nodes.clear() at the beginning of each while loop iteration to ensure only the last layer is retained.

3. Processing Queue Size Dynamically

Pitfall: Using len(leaves_queue) directly in the loop condition instead of storing it first, causing incorrect layer processing.

Issue Example:

while leaves_queue:
    remaining_nodes.clear()
    # Wrong: queue size changes during iteration
    for _ in range(len(leaves_queue)):  # This evaluates each iteration!
        leaf_node = leaves_queue.popleft()
        for neighbor in adjacency_list[leaf_node]:
            if node_degrees[neighbor] == 1:
                leaves_queue.append(neighbor)  # Queue grows during loop

Solution: Store the queue size before the loop:

current_level_size = len(leaves_queue)
for _ in range(current_level_size):
    # Process exactly current_level_size nodes

4. Incorrect Degree Update Logic

Pitfall: Checking for new leaves before decrementing the degree, or using wrong threshold.

Issue Example:

for neighbor in adjacency_list[leaf_node]:
    # Wrong order - check before update
    if node_degrees[neighbor] == 2:  # Wrong threshold
        leaves_queue.append(neighbor)
    node_degrees[neighbor] -= 1  # Should be before the check

Solution: Always decrement first, then check if degree becomes 1:

for neighbor in adjacency_list[leaf_node]:
    node_degrees[neighbor] -= 1
    if node_degrees[neighbor] == 1:  # Becomes a new leaf
        leaves_queue.append(neighbor)

5. Using Wrong Data Structure for Queue

Pitfall: Using a regular list with pop(0) instead of deque with popleft(), resulting in O(n) time complexity for each removal.

Issue Example:

leaves_queue = [node for node in range(n) if node_degrees[node] == 1]
while leaves_queue:
    leaf_node = leaves_queue.pop(0)  # O(n) operation!

Solution: Use collections.deque for O(1) operations:

from collections import deque
leaves_queue = deque(node for node in range(n) if node_degrees[node] == 1)
leaf_node = leaves_queue.popleft()  # O(1) operation