Minimum Height Trees LeetCode solution in JavaScript

1
var findMinHeightTrees = function (n, edges) {
2
  //edge case
3
  if (n <= 0) return [];
4
  if (n === 1) return [0];
5

6
  let graph = {};
7
  let indegree = Array(n).fill(0);
8
  let leaves = [];
9
  // build graph
10

11
  for (let [v, e] of edges) {
12
    //as this is undirected graph we will build indegree for both e and v
13
    if (!(v in graph)) graph[v] = [];
14
    if (!(e in graph)) graph[e] = [];
15
    graph[v].push(e);
16
    graph[e].push(v);
17
    indegree[v]++;
18
    indegree[e]++;
19
  }
20

21
  // get all nodes with indegree 1
22
  for (let i = 0; i < indegree.length; i++) {
23
    if (indegree[i] === 1) leaves.push(i);
24
  }
25

26
  let total = n;
27

28
  while (total > 2) {
29
    let size = leaves.length;
30
    // as we are removing nodes from our  total
31
    total -= size;
32

33
    for (let i = 0; i < size; i++) {
34
      let vertex = leaves.shift();
35
      for (let edge of graph[vertex]) {
36
        indegree[edge]--;
37
        if (indegree[edge] === 1) leaves.push(edge);
38
      }
39
    }
40
  }
41

42
  return leaves;
43
};