We have a binary tree with n nodes and a number k which signifies the number of nodes that we put on a set. What is the optimal algorithm to select a set consisting of k nodes, that minimizes the maximum distance of a node (of our tree) from an ancestor of his that belongs in the set we have chosen. By distance we mean the steps we have to take to get to the ancestor, if every edge has a cost of 1. For this problem we always have to take the root of the binary tree to belong in the subtree.
I have figured out, that I have to use Dynamic Programming to solve this problem, but I can't find the recursive function. I also think, to optimize the complexity, the recursive function should start from the bottom of the tree, to work its way on the top.
Edit: The nodes that belong on the set, are not necessarily connected with eachother