Leetcode 310. Minimum Height Trees

Problem Explanation:

This problem asks to find out the roots of the minimal height tree from the given undirected graph. In an undirected graph, we can choose any node as the root to result in a rooted tree, and choosing a node cleverly can minimize the height of the tree. If there is such a graph, we need to find all the roots of these minimal height trees and return their labels.

The height of a rooted tree here is defined as the number of edges on the longest path from the root to a leaf. We can assume that the edges are unique and each pair represents an undirected edge.

For example, for an undirected graph, where nodes are represented as n=4 and edges=[[1, 0], [1, 2], [1, 3]], the minimum height tree can be formed by choosing node 1 as root. So, the output would be [1].

Approach:

To solve this problem, we can use the Topological Sort pattern. We perform a breadth-first search on the graph from leaves — that is nodes with only one connection. In each step, we eliminate the current leaves together with their edges leading to them. After removing these leaves, the nodes that become the new leaves are used for the next step. This process continues until it reaches the core of the graph, which are the centroids Nodes. This is fundamentally a topological sort algorithm.

For example, consider the graph with nodes 4 and edges: [[1, 0], [1, 2], [1, 3]]

1. Create an adjacency list, a list of unordered sets to represent the graph

2. Also, create a queue and initialize with all leaf nodes (nodes with only one edge) 0 | 1 /
   2 3 Queue = [0,2,3], AdjList=[[1],[0,2,3],[1],[1]]

3. Until we're left with 1 or 2 nodes (represent minimum height trees), remove leaves, update graph and the queue with new leaves after removing current ones. Queue = [1]

4. The remaining nodes in our queue are the roots to minimum height trees, hence [1] is our answer.

Let's see how to implement this in various programming languages.

Python Solution:

1
2python
3from collections import defaultdict, deque
4class Solution:
5    def findMinHeightTrees(self, n, edges):
6        if n <= 0:
7            return []
8        if n == 1:
9            return [0]  
10        # a. Initialize the graph
11        inDegree = {i: 0 for i in range(n)}  # count of incoming edges
12        graph = defaultdict(list)  # adjacency list graph
13        # b. Build the graph
14        for edge in edges:
15            n1, n2 = edge[0], edge[1]
16            # since this is an undirected graph, therefore, add a link for both the nodes
17            graph[n1].append(n2)
18            graph[n2].append(n1)
19            # increment the in-degrees of both the nodes
20            inDegree[n1] += 1
21            inDegree[n2] += 1
22        # c. Find all leaves i.e., all nodes with only 1 inDegree
23        leaves = deque()
24        for key in inDegree:
25            if inDegree[key] == 1:
26                leaves.append(key)
27        # d. Remove leaves level by level and subtract each leave's children's inDegrees
28        # Repeat this until we are left with 1 or 2 nodes, which will be our answer
29        totalNodes = n
30        while totalNodes > 2:
31            leavesSize = len(leaves)
32            totalNodes -= leavesSize
33            for _ in range(leavesSize):
34                vertex = leaves.popleft()
35                # get the node's children to decrement their in-degrees
36                for child in graph[vertex]:
37                    inDegree[child] -= 1
38                    if inDegree[child] == 1:
39                        leaves.append(child)
40                        # return answer, containing the roots of the minimum height trees (MHTs)
41        return list(leaves)

Java Solution:

1
2java
3import java.util.*;
4class Solution {
5    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
6        if (n <= 0)
7            return new ArrayList<Integer>();
8        if (n == 1)
9            return Collections.singletonList(0);
10        // a. Initialize the graph
11        List<Integer> leaves = new ArrayList<>();
12        List<Set<Integer>> graph = new ArrayList<>();
13        for (int i = 0; i < n; i++)
14            graph.add(new HashSet<>());
15        // b. Build the graph
16        for (int[] edge : edges) {
17            int node1 = edge[0], node2 = edge[1];
18            graph.get(node1).add(node2);
19            graph.get(node2).add(node1);
20        }
21        // c. Find the leaves
22        for (int i = 0; i < graph.size(); i++) {
23            if (graph.get(i).size() == 1)
24                leaves.add(i);
25        }
26        // d. Remove leaves
27        int totalNodes = n;
28        while (totalNodes > 2) {
29            int leavesSize = leaves.size();
30            totalNodes -= leavesSize;
31            List<Integer> newLeaves = new ArrayList<>();
32            for (int i = 0; i < leavesSize; i++) {
33                int vertex = leaves.get(i);
34                int neighbor = graph.get(vertex).iterator().next();
35                // remove the leaf from graph
36                graph.get(neighbor).remove(vertex);
37                if (graph.get(neighbor).size() == 1)
38                    newLeaves.add(neighbor);
39            }
40            leaves = newLeaves;
41        }
42        return leaves;
43    }
44}

JavaScript Solution:

1
2javascript
3/**
4 * @param {number} n
5 * @param {number[][]} edges
6 * @return {number[]}
7 */
8var findMinHeightTrees = function(n, edges) {
9    if (n <= 0) 
10        return [];
11    if (n === 1)
12        return [0];
13    let inDegree = Array(n).fill(0), graph = Array.from(Array(n), () => []);
14    for (let [n1, n2] of edges) {
15        inDegree[n1] +=1; inDegree[n2] +=1;
16        graph[n1].push(n2);
17        graph[n2].push(n1);
18    }
19    let leaves = [];
20    for (let i = 0; i < inDegree.length; i++)
21        if (inDegree[i] === 1) leaves.push(i);
22    let totalNodes = n;
23    while (totalNodes > 2) {
24        let lenLeaves = leaves.length;
25        totalNodes -= lenLeaves;
26        let newLeaves = [];
27        for (let i = 0; i < lenLeaves; i++) {
28            let vertex = leaves[i];
29            let children = graph[vertex];
30            for (let child of children) {
31                inDegree[child] -= 1;
32                if (inDegree[child] === 1) newLeaves.push(child);
33            }
34        }
35        leaves = newLeaves;
36    }
37    return leaves;
38};

C++ Solution:

1
2c++
3#include <vector>
4#include <unordered_set>
5using namespace std;
6class Solution {
7 public:
8  vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
9    if (n == 1)
10      return {0};
11
12    vector<int> ans;
13    unordered_map<int, unordered_set<int>> graph;
14
15    for (const vector<int>& edge : edges) {
16      const int u = edge[0];
17      const int v = edge[1];
18      graph[u].insert(v);
19      graph[v].insert(u);
20    }
21
22    for (const auto& [label, children] : graph)
23      if (children.size() == 1)
24        ans.push_back(label);
25
26    while (n > 2) {
27      n -= ans.size();
28      vector<int> nextLeaves;
29      for (const int leaf : ans) {
30        const int u = *begin(graph[leaf]);
31        graph[u].erase(leaf);
32        if (graph[u].size() == 1)
33          nextLeaves.push_back(u);
34      }
35      ans = nextLeaves;
36    }
37
38    return ans;
39  }
40};

C# Solution:

1
2csharp
3public class Solution {
4    public IList<int> FindMinHeightTrees(int n, int[][] edges) {
5        if(n<=0) return new List<int>();
6        if(n==1) return new List<int>{0};
7       
8        List<int> res = new List<int>();
9        List<HashSet<int>> adj = new List<HashSet<int>>();
10        
11        for(int i=0; i<n; i++) adj.Add(new HashSet<int>());
12        for (int i = 0; i < edges.Length; i++) {
13            adj[edges[i][0]].Add(edges[i][1]);
14            adj[edges[i][1]].Add(edges[i][0]);
15        }
16        
17        List<int> leaves = new List<int>();
18        for (int i = 0; i < n; i++) if (adj[i].Count == 1) leaves.Add(i);
19        
20        while (n > 2) {
21            n -= leaves.Count;
22            List<int> newLeaves = new List<int>();
23            foreach(int i in leaves)
24            {
25                int j = adj[i].ElementAt(0);
26                adj[j].Remove(i);
27                if (adj[j].Count == 1) newLeaves.Add(j);
28            }
29            leaves = newLeaves;
30        }
31        return leaves;
32    }
33}

In all these language solutions, we basically follow the algorithm described in the approach. While the exact API calls are different for each language, they are all fundamentally using a breadth-first search to reduce the graph down to its minimum height.Each solution starts by initializing the graph representation, which depends on building an adjacency list. This includes recording the nodes (vertices) and their connections (edges). Next, the solutions identify the initial leaves of the tree - these are nodes with only one edge.

After setting up the graph and identifying initial leaves, the solutions turn to reducing the graph. At each iteration, the current leaves and their edges are removed from the graph. The nodes that have become leaves as a result are identified and stored for the next iteration.

This process is repeated until the total count of nodes is 1 or 2. These remaining nodes represent the roots of the minimum height trees, and are returned as the solution. The "totalNodes > 2" condition allows for graphs where multiple valid roots can lead to a minimal height tree.

In the Python, Java, JavaScript, C++ and C# implementations, breadth-first search is used in the form of dequeuing leaves, and then appending new leaves after each iteration. These implementations use dictionaries (Python), hashmaps (Java, C++, C#), and arrays (JavaScript) for storing the graph representation and leaves. Despite the variety of data structures, the logic behind the implementations is very similar and follow the Topological Sort pattern for solving this type of graph problem.