Minimum Height Trees

Companies:
  • Amazon Interview Questions

Problem Statement

For an 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.

Sample Test Cases

Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3 

Output: [1]
Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

Output: [3, 4]

Problem Solution

Gather all leaves in a queue first. At each iteration, destroy all leaves, destroy the edges that they form in the graph, then add their neighbors to the queue, iff the neighbor is a leaf.

  1. We initialize a queue of leaf nodes after creating the graph.
  2. How do we know which are leaf nodes? Keep track of in-degree using an array.
  3. Now, for the current queue of leaf nodes, we shall remove them from graph, then remove the edges they’re connected to, then update the in-degree of their neighbors.
  4. After updating the neighbor’s in-degree, see if we can add it into the queue of leaf nodes
  5. Repeat till we’ve 1 or 2 leaf nodes

Complexity Analysis

Time Complexity: O(n) Because each node will be processed exactly once. They go into the queue of leaves once, and they exit (at most) once.

Space Complexity: Graph creation takes O(E) space ie no of edges to be included.

Code Implementation

#include <bits/stdc++.h>
using namespace std;

// This class represents a undirected graph using adjacency list

class Graph
{
public:
    int V; // No. of vertices

    list<int> *adj;

    vector<int> degree;

    Graph(int V);
    void addEdge(int v, int w);
    // function to get roots which give minimum height
    vector<int> rootForMinimumHeight();
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
    for (int i = 0; i < V; i++)
        degree.push_back(0);
}

// addEdge method adds vertex to adjacency list and increases
// degree by 1
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
    adj[w].push_back(v);
    degree[v]++;
    degree[w]++;
}

// Method to return roots which gives minimum height to tree
vector<int> Graph::rootForMinimumHeight()
{
    queue<int> q;

    // first enqueue all leaf nodes in queue
    for (int i = 0; i < V; i++)
        if (degree[i] == 1)
            q.push(i);

    // loop untill total vertex remains less than 2
    while (V > 2)
    {
        for (int i = 0; i < q.size(); i++)
        {
            int t = q.front();
            q.pop();
            V--;

            // for each neighbour, decrease its degree and
            // if it become leaf, insert into queue
            list<int>::iterator j;
            for ( j = adj[t].begin(); j != adj[t].end(); j++)
            {
                degree[*j]--;
                if (degree[*j] == 1)
                    q.push(*j);
            }
        }
    }

    // copying the result from queue to result vector
    vector<int> res;
    while (!q.empty())
    {
        res.push_back(q.front());
        q.pop();
    }
    return res;
}

// Driver code to test above methods
int main()
{
    Graph g(6);
    g.addEdge(0, 3);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(4, 3);
    g.addEdge(5, 4);


    vector<int> res = g.rootForMinimumHeight();
    for (int i = 0; i < res.size(); i++)
        cout << res[i] << " ";
    cout << endl;
}

 

Scroll to Top