Grokking Graph Algorithms for Coding Interviews

0% completed

​

Problem Challenge 2: Minimum Height Trees (hard)

Problem Statement

We are given an undirected graph that has the characteristics of a k-ary tree. In such a graph, we can choose any node as the root to make a k-ary tree. The root (or the tree) with the minimum height will be called Minimum Height Tree (MHT). There can be multiple MHTs for a graph. In this problem, we need to find all those roots which give us MHTs. Write a method to find all MHTs of the given graph and return a list of their roots.

Example 1:

Input: vertices: 5, Edges: [[0, 1], [1, 2], [1, 3], [2, 4]]
Output:[1, 2]

.....

.....

.....

Like the course? Get enrolled and start learning!
D

Dylan Asoh

· 4 years ago

Could you explain more in-depth why the list of MHTs will only have one or two nodes?

W

Will

· 4 years ago

This question needs a good few diagrams to explain the 'centroid' graph finding idea, as it's not that intuitive from the description unfortunately. It may also benefit to explain the logical progression from a O(N^2) BFS or DFS brute-force idea to the optimal topological sort idea (with diagrams).

An alternate in-depth explanation of this solution exists on Leetcode here: (Q. 310: https://leetcode.com/problems/minimum-height-trees/solution/ ).

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

from collections import deque

class Solution:

  # build a unidrictional graph 
  def build_graph(self, nodes, edges):
    graph, indegree = {}, {}
    for i in range(nodes):
      graph[i] = []
      indegree[i] = 0 
    for node1, node2 in edges:
      graph[node1].append(node2)
      graph[node2].append(node1)
      indegree[node1] += 1
      indegree[node2] += 1
    return(graph, indegree)
   
  def findTrees(self, nodes, edges):
    if nodes == 1:
      return [0]

    graph, indegree = self.build_graph(nodes, edges)
    q = deque([x for x in indegree if indegree[x] == 1])

    result = []
    
    # topological ordering can be done on unidirectional graph too
    # for that we should do indegree[neighbor] == 1 as edge nodes are linked
    # topological finds the center
A

Alan Lo

· 3 years ago

Can you add images to explain main solution with the 'P' root tree and 'M' subtree description? Thanks

J

J

· 4 years ago

Python3 solution fails on test case { nodes = 3, edges = [[0,1],[0,2]] } on LeetCode for LC 310. Minimum Height Trees ( https://leetcode.com/problems/minimum-height-trees/ ).

Show 2 replies