Given a tree with N nodes value from 1 to N and (N – 1) Edges and a number K, the task is to remove the minimum number of nodes from the tree such that every subtree will have at most K nodes. Removing Nodes will remove the edges from that nodes to all the other connected nodes.
Examples:
Input: N = 10, K = 3, Below is the graph:
Output:
Number of nodes removed: 2
Removed Nodes: 2 1
Explanation:
After removing the nodes 1 and 2, here, no subtree or tree has more than 3 nodes. Below is the resulting graph:
Input: N = 6, K = 3, Below is the graph:
Output:
Number of nodes removed: 1
Removed Nodes: 1
Explanation:
After removing the nodes 1, here, no subtree or tree has more than 3 nodes. Below is the resulting graph:
Approach: The idea is to observe that the number of nodes in the subtree of a node X is the sum of the number of nodes in the subtree of its children and the node itself. Below are the steps:
- Use Dynamic Programming and DFS to store the count of nodes in the subtree of each node easily.
- Now, to have no node with subtree having more than K nodes, the idea is to remove the node whenever it has more than K nodes in its subtree, and pass 0 to its parent.
- In the above step, we are having each node with nodes in its subtree not greater than K and minimizing the number of node removals.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define N 20// Function to perform DFS Traversalint dfs(vector<bool> &visited, int s, int &K, int &removals, vector<int> &removed_nodes, vector<vector<int>> &adj) { // Mark the node as true visited[s] = true; int nodes = 1; // Traverse adjacency list // of child node for(int child : adj[s]) { // If already visited then // omit the node if (visited[child]) continue; // Add number of nodes // in subtree nodes += dfs(visited, child, K, removals, removed_nodes, adj); } if (nodes > K) { // Increment the count removals++; removed_nodes.push_back(s); nodes = 0; } // Return the nodes return nodes;}// Function to add edges in graphvoid addEdge(vector<vector<int>> &adj, int a, int b) { adj[a].push_back(b); adj[b].push_back(a);}// Function that finds the number// of nodes to be removed such that// every subtree has size at most Kvoid findRemovedNodes(vector<bool> &visited, int K, int &removals, vector<int> &removed_nodes, vector<vector<int>> &adj){ // Function Call to find the // number of nodes to remove dfs(visited, 1, K, removals, removed_nodes, adj); // Print Removed Nodes cout << "Number of nodes removed: " << removals << endl; cout << "Removed Nodes: "; for(int node : removed_nodes) { cout << node << " "; }}// Driver Codeint main() { // Variables used to store data globally vector<bool> visited(N); int K; int removals = 0; vector<int> removed_nodes; // Adjacency list representation of tree vector<vector<int>> adj(N); // Insert of nodes in graph addEdge(adj, 1, 2); addEdge(adj, 1, 3); addEdge(adj, 2, 4); addEdge(adj, 2, 5); addEdge(adj, 3, 6); // Required subtree size K = 3; // Function Call findRemovedNodes(visited, K, removals, removed_nodes, adj); return 0;}// This code is contributed by sanjeev2552 |
Java
// Java program for the above approachimport java.util.*;class GFG { // Variables used to store data globally static final int N = 20; static boolean visited[] = new boolean[N]; static int K; static int removals = 0; static ArrayList<Integer> removed_nodes = new ArrayList<>(); // Adjacency list representation of tree static ArrayList<ArrayList<Integer> > adj = new ArrayList<>(); // Function to perform DFS Traversal static int dfs(int s) { // Mark the node as true visited[s] = true; int nodes = 1; // Traverse adjacency list // of child node for (Integer child : adj.get(s)) { // If already visited then // omit the node if (visited[child]) continue; // Add number of nodes // in subtree nodes += dfs(child); } if (nodes > K) { // Increment the count removals++; removed_nodes.add(s); nodes = 0; } // Return the nodes return nodes; } // Function to add edges in graph static void addEdge(int a, int b) { adj.get(a).add(b); adj.get(b).add(a); } // Function that finds the number // of nodes to be removed such that // every subtree has size at most K public static void findRemovedNodes(int K) { // Function Call to find the // number of nodes to remove dfs(1); // Print Removed Nodes System.out.println("Number of nodes" + " removed: " + removals); System.out.print("Removed Nodes: "); for (int node : removed_nodes) System.out.print(node + " "); } // Driver Code public static void main(String[] args) { // Creating list for all nodes for (int i = 0; i < N; i++) adj.add(new ArrayList<>()); // Insert of nodes in graph addEdge(1, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); addEdge(3, 6); // Required subtree size K = 3; // Function Call findRemovedNodes(K); }} |
Python3
# Python3 program for the above approach# Variables used to store data globallyN = 20visited = [False for i in range(N)]K = 0removals = 0removed_nodes = []# Adjacency list representation of treeadj = [[] for i in range(N)]# Function to perform DFS Traversaldef dfs(s): global removals # Mark the node as true visited[s] = True nodes = 1 # Traverse adjacency list # of child node for child in adj[s]: # If already visited then # omit the node if (visited[child]): continue # Add number of nodes # in subtree nodes += dfs(child) if (nodes > K): # Increment the count removals += 1 removed_nodes.append(s) nodes = 0 # Return the nodes return nodes# Function to add edges in graphdef addEdge(a, b): adj[a].append(b) adj[b].append(a)# Function that finds the number# of nodes to be removed such that# every subtree has size at most Kdef findRemovedNodes(K): # Function Call to find the # number of nodes to remove dfs(1) # Print Removed Nodes print("Number of nodes removed: ", removals) print("Removed Nodes: ", end = ' ') for node in removed_nodes: print(node, end = ' ') # Driver Codeif __name__ == "__main__": # Insert of nodes in graph addEdge(1, 2) addEdge(1, 3) addEdge(2, 4) addEdge(2, 5) addEdge(3, 6) # Required subtree size K = 3 # Function Call findRemovedNodes(K)# This code is contributed by rutvik_56 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Variables used to store data globally static readonly int N = 20; static bool []visited = new bool[N]; static int K; static int removals = 0; static List<int> removed_nodes = new List<int>(); // Adjacency list representation of tree static List<List<int> > adj = new List<List<int>>(); // Function to perform DFS Traversal static int dfs(int s) { // Mark the node as true visited[s] = true; int nodes = 1; // Traverse adjacency list // of child node foreach (int child in adj[s]) { // If already visited then // omit the node if (visited[child]) continue; // Add number of nodes // in subtree nodes += dfs(child); } if (nodes > K) { // Increment the count removals++; removed_nodes.Add(s); nodes = 0; } // Return the nodes return nodes; } // Function to add edges in graph static void addEdge(int a, int b) { adj[a].Add(b); adj[b].Add(a); } // Function that finds the number // of nodes to be removed such that // every subtree has size at most K public static void findRemovedNodes(int K) { // Function Call to find the // number of nodes to remove dfs(1); // Print Removed Nodes Console.WriteLine("Number of nodes" + " removed: " + removals); Console.Write("Removed Nodes: "); foreach (int node in removed_nodes) Console.Write(node + " "); } // Driver Code public static void Main(String[] args) { // Creating list for all nodes for (int i = 0; i < N; i++) adj.Add(new List<int>()); // Insert of nodes in graph addEdge(1, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); addEdge(3, 6); // Required subtree size K = 3; // Function Call findRemovedNodes(K); }}// This code is contributed by Rohit_ranjan |
Javascript
<script> // JavaScript program for the above approach // Variables used to store data globally let N = 20; let visited = new Array(N); let K; let removals = 0; let removed_nodes = []; // Adjacency list representation of tree let adj = []; // Function to perform DFS Traversal function dfs(s) { // Mark the node as true visited[s] = true; let nodes = 1; // Traverse adjacency list // of child node for(let child = 0; child < adj[s].length; child++) { // If already visited then // omit the node if (visited[adj[s][child]]) continue; // Add number of nodes // in subtree nodes += dfs(adj[s][child]); } if (nodes > K) { // Increment the count removals++; removed_nodes.push(s); nodes = 0; } // Return the nodes return nodes; } // Function to add edges in graph function addEdge(a, b) { adj[a].push(b); adj[b].push(a); } // Function that finds the number // of nodes to be removed such that // every subtree has size at most K function findRemovedNodes(K) { // Function Call to find the // number of nodes to remove dfs(1); // Print Removed Nodes document.write("Number of nodes" + " removed: " + removals + "</br>"); document.write("Removed Nodes: "); for(let node = 0; node < removed_nodes.length; node++) document.write(removed_nodes[node] + " "); } // Creating list for all nodes for (let i = 0; i < N; i++) adj.push([]); // Insert of nodes in graph addEdge(1, 2); addEdge(1, 3); addEdge(2, 4); addEdge(2, 5); addEdge(3, 6); // Required subtree size K = 3; // Function Call findRemovedNodes(K);</script> |
Output
Number of nodes removed: 1 Removed Nodes: 1
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
