Minimum number of nodes to be removed such that no subtree has more than K nodes

Internship at OpenGenus

Get FREE domain for 1st year and build your brand new site

We will be given a tree with N Nodes and N-1 edges and the number K. We have to find minimum numbers of Nodes that we have to need to deleted in order to make total numbers of node in every subtree less then or equal to K.

This problem can be solved in O(V^2) time and using the idea of Depth First Search.

Lets understand with few examples

Example 1

consider the following tree with 6 Nodes and 5 Edges

untitled

lets the value of K be 3 so for this case if we want all the subtree having total nodes less then or equal to K then we need to delete anyone from 0 or 1 lets we have deleted 0, then after deleting we will get our result as following

untitled-1-

result will be two subtree contaning total nodes less then or equal to K.

Example 2

consider the following tree with 11 Nodes and 10 Edges

untitled-2-

lets the value of K be 3 so for this case if we want all the subtree having total nodes less then or equal to K then we need to delete two nodes 1 or 5 , after deleting we will get our result as following

untitled-3-

result will be three subtree contaning total nodes less then or equal to K.

After deleting vertices the connected edges with that vertices also get deleted

Implementation

For implementing this we will use Graph data structure and we will apply Depth First Search algorithm with some little modification for creating graph we will use adjency matrix.

  • In normal dfs function we use dynamic programming for storing visited nodes so that we can skip those nodes if they get called again. this will improve its time complexity.
  • In this we will add another container so that we can store removed element in that.
  • Also instead of returning void we will return total number of child node including parent node for that particular node. if the node is leaf node then it will return [1 (count for current node) + 0 (zero child node)] and if node is not leaf node then it will return [1 (count for current node) + count returned by child nodes of particular node ]
  • If total number of child node get greater then k then we will add that element into removed elements container and set total child nodes equal to 0 for node who called removed node.

Steps

Writing DFS function:

  • We have to first check that all of the child nodes with that node and call them with the same dfs function with starting vertex as the child node. first we will take our starting vertex as root.

  • After calling we will compare the returned count value weather it is greater or less than k.
    of it is less than k then we will return that by adding count of current node

  • If count is greater than k then we will set count for current node to 0, and also we will add current node to removed node list because subtree for current node is greater then k.

  • Also at the start of the function we will check that the current node is leaf node or not, if it is leaf node then we will return 1 (count for that node only).

Code:

#include<bits/stdc++.h>
using namespace std;
//dfs function
int dfs(int **a, int n, int sv, bool *visited, set<int> &ss, int k)
{
  int count=1;
  visited[sv] = true;
  for(int i=0; i<n; i++)
  {
    if(a[sv][i] == 1 && !visited[i]) count += dfs(a, n, i, visited, ss, k);
  }
  if(count>k)
  {
    ss.insert(sv);
    count = 0;
  }
  return count;
}

int main()
{
  int n, e, k;     // n = number of nodes, e = number of edges, k = max nodes in subtrees
  cin>>n>>e>>k;
  // creating graph
  int **a = new int*[n];
  for(int i=0; i<n; i++)
  {
    a[i] = new int[n];
    for(int j=0; j<n; j++) a[i][j] = 0;
  }
  int f, s;
  for(int i=0; i<e; i++)
  {
    cin>>f>>s;
    a[f][s] = 1; a[s][f] = 1;
  }
  bool *visited = new bool[n];
  for(int i=0; i<n; i++) visited[i] = false;
  set<int> ss;
  //calling function dfs
  int count = dfs(a, n, 0, visited, ss, k); cout<<endl;
  if(count>k) ss.insert(0);
  cout<<"min no of element: "<<ss.size()<<endl;
  cout<<"elements: ";
  for(int i:ss) cout<<i<<" "; cout<<endl;

  //clearing data
  for(int i=0;i<n;i++) delete [] a[i];
  delete [] a;
  delete [] visited;
  return 0;
}

Input:

below input is graph in Example 2

11 10 3
0 1
0 2
2 4
1 3
3 5
3 6
6 8
5 7
7 9
7 10

Output:

min no of element: 2
elements: 1 5

Time Complexity:

  • If we apply BFS using Adjency List then Time complexity will be O(V+E).
  • If we apply BFS using Adjency Matrix for this the time complexity will be O(V^2).

For the above example

  • Time Complexity will be O(V * V)
  • Space Complexity will be O(V * V)

With this article at OpenGenus, you must have the complete idea of finding minimum number of nodes to be removed such that no subtree has more than K nodes.