algoadvance

Leetcode 310. Minimum Height Trees

Problem Statement

Given an undirected graph with n nodes labeled from 0 to n-1, and an array of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi, you need to find all the nodes that can be the root of a Minimum Height Tree (MHT). A Minimum Height Tree is a tree with the minimum possible height.

Clarifying Questions

  1. Input Constraints:
    • What are the limits on n and the length of edges?
      • 1 <= n <= 2 * 10^4
      • edges.length == n - 1
      • 0 <= ai, bi < n
      • ai != bi
      • All pairs (ai, bi) are unique.
  2. Graph Characteristics:
    • The graph is always connected and has n-1 edges, indicating that it is a tree.

With these constraints in mind, let’s move forward to the strategy.

Strategy

  1. Initial Observations:
    • The problem can be visualized as finding the “centers” of the tree as the root nodes that result in the minimum height.
  2. Degree Reduction (Pruning) Technique:
    • Start by identifying all the leaf nodes (nodes with degree 1).
    • Iteratively remove the leaf nodes and update the degrees of their neighbors.
    • Continue this process until 1 or 2 nodes are left. These nodes are the centroids of the graph, representing the roots of the Minimum Height Trees.
  3. Steps:
    • Initialize a graph using adjacency lists.
    • Identify all leaf nodes.
    • Iteratively prune the tree from the leaves inward.
    • Return the remaining nodes, which are the centroids.

Code

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
    if (n == 1) return {0};
    
    vector<vector<int>> adj(n);
    vector<int> degree(n, 0);
    
    // Build the adjacency list and degree of each node.
    for (auto& edge : edges) {
        adj[edge[0]].emplace_back(edge[1]);
        adj[edge[1]].emplace_back(edge[0]);
        degree[edge[0]]++;
        degree[edge[1]]++;
    }
    
    queue<int> leaves;
    // Collect all initial leaves
    for (int i = 0; i < n; ++i) {
        if (degree[i] == 1) {
            leaves.push(i);
        }
    }
    
    int remainingNodes = n;
    // Trim the leaves until one or two nodes remain
    while (remainingNodes > 2) {
        int leavesCount = leaves.size();
        remainingNodes -= leavesCount;
        for (int i = 0; i < leavesCount; ++i) {
            int leaf = leaves.front();
            leaves.pop();
            // Decrease the degree of connected nodes
            for (int neighbor : adj[leaf]) {
                degree[neighbor]--;
                if (degree[neighbor] == 1) {
                    leaves.push(neighbor);
                }
            }
        }
    }
    
    vector<int> result;
    while (!leaves.empty()) {
        result.push_back(leaves.front());
        leaves.pop();
    }
    
    return result;
}

Time Complexity

Thus, the overall time complexity of the solution is (O(n)), which is efficient given the constraints.

Summary

To solve the Minimum Height Trees problem, we repeatedly prune the leaves of the tree until 1 or 2 nodes remain, which are the centroids. This approach ensures that we identify the roots of the minimum height trees efficiently in linear time.

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