In this paper we deal with the Critical Node Problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the number of connections between pairs of nodes in the residual graph. While the NP-completeness of this problem for general graphs has been already established in [1], here we study the subclass of CNP over trees. We will prove that weighted CNP over trees is still NP-complete, while the unweighted version can be proved to be solvable in polynomial time through a dynamic programming approach.