Minimum number of Nodes to be removed such that no subtree has more than K nodes | Java program for the above approach ; Variables used to store data globally ; Adjacency list representation of tree ; Function to perform DFS Traversal ; Mark the node as true ; Traverse adjacency list of child node ; If already visited then omit the node ; Add number of nodes in subtree ; Increment the count ; Return the nodes ; Function to add edges in graph ; Function that finds the number of nodes to be removed such that every subtree has size at most K ; Function Call to find the number of nodes to remove ; Print Removed Nodes ; Driver Code ; Creating list for all nodes ; Insert of nodes in graph ; Required subtree size ; Function Call
import java . util . * ; class GFG { 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 < > ( ) ; static ArrayList < ArrayList < Integer > > adj = new ArrayList < > ( ) ; static int dfs ( int s ) { visited [ s ] = true ; int nodes = 1 ; for ( Integer child : adj . get ( s ) ) { if ( visited [ child ] ) continue ; nodes += dfs ( child ) ; } if ( nodes > K ) { removals ++ ; removed_nodes . add ( s ) ; nodes = 0 ; } return nodes ; } static void addEdge ( int a , int b ) { adj . get ( a ) . add ( b ) ; adj . get ( b ) . add ( a ) ; } public static void findRemovedNodes ( int K ) { dfs ( 1 ) ; System . out . println ( " Number ▁ of ▁ nodes " + " ▁ removed : ▁ " + removals ) ; System . out . print ( " Removed ▁ Nodes : ▁ " ) ; for ( int node : removed_nodes ) System . out . print ( node + " ▁ " ) ; } public static void main ( String [ ] args ) { for ( int i = 0 ; i < N ; i ++ ) adj . add ( new ArrayList < > ( ) ) ; addEdge ( 1 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 2 , 4 ) ; addEdge ( 2 , 5 ) ; addEdge ( 3 , 6 ) ; K = 3 ; findRemovedNodes ( K ) ; } }