310. Minimum Height Trees

Description

You are given an undirected graph represented by n nodes, where n is the number of nodes. The edges of the graph are given in a 2D list edges, where each element is a pair [a, b] representing an edge between nodes a and b. The task is to find all possible root nodes of the Minimum Height Trees (MHTs) that can be formed. A tree's height is defined as the number of edges on the longest path from the root to any leaf. A Minimum Height Tree (MHT) has the smallest possible height among all trees formed from the graph.

Intuition

The problem can be understood as finding the "center" of the graph, which is the optimal root(s) for the MHT.

• If we imagine peeling off leaves from the tree, layer by layer, the root of the MHT will eventually emerge as the last remaining node(s).
• This approach works because leaves (nodes with only one edge) have the least effect on the tree's height, and the core of the graph will naturally minimize the tree height.

Approach

1. Special Case: - If there is only one node (n == 1), the answer is simply [0].
2. Graph Representation: - Represent the graph using an adjacency list where each node points to its neighbors.
3. Track Leaves: - Identify all the leaves in the graph. A leaf is a node that has only one connection (i.e., one neighbor).
4. Peel Off Layers: - Start removing leaves iteratively. Once a leaf is removed, the neighboring node’s degree is reduced by 1. If any of those neighbors become leaves (i.e., their degree becomes 1), add them to the leaves queue.
5. End Condition: - Repeat the process until there are two or fewer nodes left in the graph. These remaining nodes are the root nodes of the Minimum Height Trees.
6. Return the Remaining Nodes: - The final remaining nodes are the centers of the graph and represent the roots of the Minimum Height Trees.

Complexity

Time Complexity:

• The time complexity is (O(n)), where (n) is the number of nodes. This is because each node and each edge is processed only once during the traversal of the graph.

Space Complexity:

• The space complexity is (O(n)), which is needed to store the adjacency list and the degrees of the nodes. We also use extra space for the leaves queue, but it is bounded by (n).

Code

C++

class Solution {
public:
    vector findMinHeightTrees(int n, vector>& edges) {
        if (n == 1) return {0};

        unordered_map> adj;
        for (int i = 0; i < n; i++) {
            adj[i] = vector();
        }
        // Populate adjacency list
        for (const auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }

        unordered_map edgeCount;
        queue leaves;

        for (auto& [src, neighbors] : adj) {
            if (neighbors.size() == 1) {
                leaves.push(src);
            }
            edgeCount[src] = neighbors.size();
        }

        // Reduce the graph iteratively
        while (!leaves.empty()) {
            if (n <= 2) {
                vector result;
                while (!leaves.empty()) {
                    result.push_back(leaves.front());
                    leaves.pop();
                }
                return result;
            }

            int len = leaves.size();
            for (int i = 0; i < len; i++) {
                int node = leaves.front();
                leaves.pop();
                n--;

                for (int nei : adj[node]) {
                    edgeCount[nei]--;
                    if (edgeCount[nei] == 1) {
                        leaves.push(nei);
                    }
                }
            }
        }
        return {};
    }
};

Python

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

        adj = defaultdict(list)
        for n1, n2 in edges:
            adj[n1].append(n2)
            adj[n2].append(n1)

        edge_count = {}
        leaves = deque()

        for src, neighbors in adj.items():
            if len(neighbors) == 1:
                leaves.append(src)
            edge_count[src] = len(neighbors)

        # Reduce the graph iteratively
        while leaves:
            if n <= 2:
                return list(leaves)

            len_leaves = len(leaves)
            for _ in range(len_leaves):
                node = leaves.popleft()
                n -= 1

                for nei in adj[node]:
                    edge_count[nei] -= 1
                    if edge_count[nei] == 1:
                        leaves.append(nei)

        return []

Java

class Solution {
    public List findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Arrays.asList(0);

        Map> adj = new HashMap<>();
        for (int i = 0; i < n; i++) {
            adj.put(i, new ArrayList<>());
        }

        // Populate adjacency list
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        Map edgeCount = new HashMap<>();
        Queue leaves = new LinkedList<>();

        for (Map.Entry> entry : adj.entrySet()) {
            int src = entry.getKey();
            List neighbors = entry.getValue();
            if (neighbors.size() == 1) {
                leaves.offer(src);
            }
            edgeCount.put(src, neighbors.size());
        }

        // Reduce the graph iteratively
        while (!leaves.isEmpty()) {
            if (n <= 2) {
                return new ArrayList<>(leaves);
            }

            int len = leaves.size();
            for (int i = 0; i < len; i++) {
                int node = leaves.poll();
                n--;

                for (int nei : adj.get(node)) {
                    edgeCount.put(nei, edgeCount.get(nei) - 1);
                    if (edgeCount.get(nei) == 1) {
                        leaves.offer(nei);
                    }
                }
            }
        }
        return new ArrayList<>();
    }
}

JavaScript

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[]}
 */
var findMinHeightTrees = function(n, edges) {
    if (n === 1 || !edges) return [0]

    const adj = {}
    for (let i = 0; i < n; i ++) {
        adj[i] = []
    }
    //populate map
    for (let [n1,n2] of edges) {
        if (adj[n1]) adj[n1].push(n2)
        if (adj[n1]) adj[n2].push(n1)
    }
    const edgeCount = {}
    let leaves = [] // queue
    for (let [src, neighbor] of Object.entries(adj)) {
        if (neighbor.length === 1) {
            leaves.push(src)

        }
        edgeCount[src] = neighbor.length
    }

    // build graph with queue
    while (leaves.length) {
        if ( n <= 2){
            return leaves
        }

        let len = leaves.length
        for (let i = 0; i < len; i++) {
            let node = leaves.shift()
            console.log(node)
            n -=1
            
            for (let nei of adj[node]) {
                edgeCount[nei] -=1
                if (edgeCount[nei] === 1) {
                    leaves.push(nei)
                }
            }
        }
    }
};