minimum-height-trees.js

/**
 * For a undirected graph with tree characteristics, we can choose any node as the root.
 * The result graph is then a rooted tree. Among all possible rooted trees,
 * those with minimum height are called minimum height trees (MHTs). Given such a graph,
 * write a function to find all the MHTs and return a list of their root labels.
 *
 * Format
 * The graph contains n nodes which are labeled from 0 to n - 1. You will be given the
 * number n and a list of undirected edges (each edge is a pair of labels).
 *
 * You can assume that no duplicate edges will appear in edges. Since all edges are
 * undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
 *
 * Example 1:
 *
 * Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]
 *
 *         0
 *         |
 *         1
 *        / \
 *       2   3
 *
 * return [1]
 *
 * Example 2:
 *
 * Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
 *
 *      0  1  2
 *       \ | /
 *         3
 *         |
 *         4
 *         |
 *         5
 *
 * return [3, 4]
 *
 * Note:
 *
 * (1) According to the definition of tree on Wikipedia: “a tree is an undirected graph
 * in which any two vertices are connected by exactly one path. In other words, any
 * connected graph without simple cycles is a tree.”
 *
 * (2) The height of a rooted tree is the number of edges on the longest downward path
 * between the root and a leaf.
 */

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[]}
 */
const findMinHeightTrees = (n, edges) => {
  if (n === 1) {
    return [0];
  }

  // Step 1. Build the graph
  const adjList = buildGraph(n, edges);

  // Step 2. Perform BFS by removing leaves until there are only two leaves left
  const leaves = [];

  for (let i = 0; i < n; i++) {
    if (adjList.get(i).size === 1) {
      leaves.push(i);
    }
  }

  while (n > 2) {
    const size = leaves.length;

    n -= size;

    for (let i = 0; i < size; i++) {
      const u = leaves.shift();

      adjList.get(u).forEach(v => {
        adjList.get(v).delete(u);

        if (adjList.get(v).size === 1) {
          leaves.push(v);
        }
      });
    }
  }

  return leaves;
};

const buildGraph = (n, edges) => {
  const adjList = new Map();

  for (let i = 0; i < n; i++) {
    adjList.set(i, new Set());
  }

  edges.forEach(edge => {
    const u = edge[0];
    const v = edge[1];

    adjList.get(u).add(v);
    adjList.get(v).add(u);
  });

  return adjList;
};

export default findMinHeightTrees;