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 ; Driver Code ;  ; Insert of nodes in graph ; Required subtree size ; Function Call
N = 20 NEW_LINE visited = [ False for i in range ( N ) ] NEW_LINE K = 0 NEW_LINE removals = 0 NEW_LINE removed_nodes = [ ] NEW_LINE adj = [ [ ] for i in range ( N ) ] NEW_LINE def dfs ( s ) : NEW_LINE INDENT global removals NEW_LINE visited [ s ] = True NEW_LINE nodes = 1 NEW_LINE for child in adj [ s ] : NEW_LINE INDENT if ( visited [ child ] ) : NEW_LINE INDENT continue NEW_LINE DEDENT nodes += dfs ( child ) NEW_LINE DEDENT if ( nodes > K ) : NEW_LINE INDENT removals += 1 NEW_LINE removed_nodes . append ( s ) NEW_LINE nodes = 0 NEW_LINE DEDENT return nodes NEW_LINE DEDENT def addEdge ( a , b ) : NEW_LINE INDENT adj [ a ] . append ( b ) NEW_LINE adj [ b ] . append ( a ) NEW_LINE DEDENT def findRemovedNodes ( K ) : NEW_LINE INDENT dfs ( 1 ) NEW_LINE print ( " Number ▁ of ▁ nodes ▁ removed : ▁ " , removals ) NEW_LINE print ( " Removed ▁ Nodes : ▁ " , end = ' ▁ ' ) NEW_LINE for node in removed_nodes : NEW_LINE INDENT print ( node , end = ' ▁ ' ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE / * Creating list for all nodes * / NEW_LINE INDENT addEdge ( 1 , 2 ) NEW_LINE addEdge ( 1 , 3 ) NEW_LINE addEdge ( 2 , 4 ) NEW_LINE addEdge ( 2 , 5 ) NEW_LINE addEdge ( 3 , 6 ) NEW_LINE K = 3 NEW_LINE findRemovedNodes ( K ) NEW_LINE DEDENT