algoadvance

Leetcode 310. Minimum Height Trees

Problem Statement

Given a tree with n nodes, labeled from 0 to n-1, and an array of n-1 edges where edges[i] = [a_i, b_i] indicates an undirected edge between nodes a_i and b_i, you need to find the roots of the Minimum Height Trees (MHTs). A tree’s height is determined as the number of edges in the longest path from the root to any leaf. Your task is to return a list of possible root nodes for the MHTs.

Example:

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

Output: [1]

Constraints:

Clarifying Questions

  1. What is the format of the output?
    • The output should be a list of node indices which are the roots of the Minimum Height Trees.
  2. Can the tree be empty?
    • No, the constraint states that 1 <= n, so there’s at least one node.
  3. Should we handle invalid inputs?
    • The problem guarantees that the input is a valid tree, so no need to handle invalid cases.

Strategy

  1. This problem essentially requires finding the “centroid” of the tree. The concept is to remove leaf nodes layer by layer and focus on the center. In practice:
    1. Initialize each node’s degree (number of connections).
    2. Identify leaf nodes (nodes with only one connection).
    3. Iteratively remove leaf nodes and update the degrees of their neighbors until 2 or fewer nodes remain.
    4. The remaining nodes are the roots of the MHTs.
  2. We’ll use a Breadth-First Search (BFS) to prune the tree layer by layer.

Code

import java.util.*;

public class MinimumHeightTrees {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Collections.singletonList(0);
        
        // Build the graph using adjacency list
        List<Set<Integer>> graph = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            graph.add(new HashSet<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        
        // Initialize the first layer of leaves
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (graph.get(i).size() == 1) {
                leaves.add(i);
            }
        }
        
        // Trim the leaves until we reach the core of the graph
        int remainingNodes = n;
        while (remainingNodes > 2) {
            remainingNodes -= leaves.size();
            List<Integer> newLeaves = new ArrayList<>();
            for (int leaf : leaves) {
                int neighbor = graph.get(leaf).iterator().next();
                graph.get(neighbor).remove(leaf);
                if (graph.get(neighbor).size() == 1) {
                    newLeaves.add(neighbor);
                }
            }
            leaves = newLeaves;
        }
        
        return leaves;
    }
    
    public static void main(String[] args) {
        MinimumHeightTrees mht = new MinimumHeightTrees();
        int n = 4;
        int[][] edges = // use example above
        System.out.println(mht.findMinHeightTrees(n, edges));  // Output: [1]
    }
}

Time Complexity

Overall, the time complexity is O(n), which is efficient for the input constraints (1 <= n <= 2 * 10^4).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI