Minimum number of Nodes to be removed such that no subtree has more than K nodes | 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 ; Creating list for all nodes ; Insert of nodes in graph ; Required subtree size ; Function Call
let N = 20 ; let visited = new Array ( N ) ; let K ; let removals = 0 ; let removed_nodes = [ ] ; let adj = [ ] ; function dfs ( s ) { visited [ s ] = true ; let nodes = 1 ; for ( let child = 0 ; child < adj [ s ] . length ; child ++ ) { if ( visited [ adj [ s ] [ child ] ] ) continue ; nodes += dfs ( adj [ s ] [ child ] ) ; } if ( nodes > K ) { removals ++ ; removed_nodes . push ( s ) ; nodes = 0 ; } return nodes ; } function addEdge ( a , b ) { adj [ a ] . push ( b ) ; adj [ b ] . push ( a ) ; } function findRemovedNodes ( K ) { dfs ( 1 ) ; document . write ( " " + " " + removals + " " ) ; document . write ( " " ) ; for ( let node = 0 ; node < removed_nodes . length ; node ++ ) document . write ( removed_nodes [ node ] + " " ) ; } for ( let i = 0 ; i < N ; i ++ ) adj . push ( [ ] ) ; addEdge ( 1 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 2 , 4 ) ; addEdge ( 2 , 5 ) ; addEdge ( 3 , 6 ) ; K = 3 ; findRemovedNodes ( K ) ;