Minimum Height Trees

To solve this coding challenge, we need to find the root labels of the Minimum Height Trees (MHTs) in a given tree. The goal is to identify these roots such that the resultant tree height is minimized. Here's a detailed step-by-step explanation of the methodology to solve this problem:

# Explanation

1. Understanding the Tree Structure :
• A tree is defined as a connected graph without cycles.
• Given a number of nodes
  n
  and an array
  edges
  , which lists the edges between nodes, our tree is represented.
2. Identifying MHTs :
• When choosing nodes as root, a Minimum Height Tree (MHT) is one where the height is minimal.
• The problem requires us to return all possible root nodes that form a Minimum Height Tree.
3. Special Cases :
• If
  n
  is 1, the only node itself is the MHT root.
• If
  n
  is 2, both nodes are MHT roots since either can be the root.
4. Core Strategy :
• The central idea involves repeatedly pruning leaf nodes until we are left with the centroids.
• Leaves are nodes with only one connection (degree 1 in graph terms).
5. Algorithm :
• Build the graph using adjacency lists from the edges.
• Initialize a queue to store all leaf nodes.
• Iteratively remove leaf nodes and update the degrees of neighboring nodes.
• If a neighboring node becomes a leaf (degree 1), add it to the queue.
• Continue until 2 or fewer nodes remain.
• These remaining nodes will be our MHT roots.

Detailed Steps in Pseudocode

                                            
Function findMinHeightTrees(n, edges):
    # If the number of nodes is 1 or 2, return all nodes as MHT roots.
    If n <= 2:
        Return list(range(n))
    End If

    # Step 1: Build the graph using adjacency list representation.
    neighbors = defaultdict(set)
    For each edge in edges:
        u, v = edge
        neighbors[u].add(v)
        neighbors[v].add(u)
    End For

    # Step 2: Initialize a deque to store all leaf nodes.
    leaves = deque()
    For each node in range(n):
        If len(neighbors[node]) == 1:
            leaves.append(node)
        End If
    End For

    # Step 3: Iteratively remove leaf nodes.
    remaining_nodes = n
    While remaining_nodes > 2:
        leaves_count = len(leaves)
        remaining_nodes -= leaves_count

        For i in range(leaves_count):
            leaf = leaves.popleft()
            neighbor = neighbors[leaf].pop()  # Get the single neighbor
            neighbors[neighbor].remove(leaf)  # Remove the leaf from the neighbor's list

            # If the neighbor becomes a leaf, add it to the deque.
            If len(neighbors[neighbor]) == 1:
                leaves.append(neighbor)
            End If
        End For
    End While

    # The remaining nodes are the roots of the Minimum Height Trees.
    Return list(leaves)
End Function

                                        

# Detailed Pseudocode Breakdown

Step 1: Build the Graph

• neighbors = defaultdict(set) : This initializes an adjacency list to store each node's neighbors.
• for each edge in edges : Loop through each edge to add it to the adjacency list.

Step 2: Identify Leaf Nodes

• leaves = deque() : Initialize a deque to hold current leaf nodes.
• for each node in range(n) : Check each node's degree (number of connections).
• if len(neighbors[node]) == 1 : If the node is a leaf (has one neighbor), add it to
  leaves
  .

Step 3: Pruning Leaf Nodes

• while remaining_nodes > 2 : Continue until we have 2 or fewer nodes.
• leaves_count = len(leaves) : Get the number of current leaves.
• remaining_nodes -= leaves_count : Update count after removing current leaves.
• leaf = leaves.popleft() : Remove and process each leaf.
• neighbor = neighbors[leaf].pop() : Get and remove the single neighbor of the leaf.
• neighbors[neighbor].remove(leaf) : Remove the leaf from the neighbor's adjacency list.
• if len(neighbors[neighbor]) == 1 : If this neighbor is now a leaf, add it to
  leaves
  .

Final Return:

• return list(leaves) : The remaining nodes are the roots of the Minimum Height Trees.

This detailed approach ensures that we efficiently identify the MHT roots by leveraging properties of trees and graph traversal techniques.