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

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 examplesExample 1

consider the following tree with 6 Nodes and 5 Edges

[image error]

lets the value of K be 3 so for this case if we want all the subtree having total nodes less th...