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

  • $\begingroup$ the "distance" is quite unclear to me. Do you mean the depth of the subtree ? You say "that minimizes the maximum distance of a node". What "a" stands for ? $\endgroup$ – Optidad Dec 11 '19 at 13:26
  • $\begingroup$ @Vince I edited my question to make it clearer (I hope). By distance I mean how many nodes you have to pass through to reach an ancestor node that belongs to the set of k nodes $\endgroup$ – user102382 Dec 11 '19 at 15:13
  • $\begingroup$ Hint : Instead of trying to solve this problem, try to solve the following : Can I select $k$ nodes or less so that the maximum distance to a chosen ancestor is at most $d$? Once you have solved this problem, I'm sure you can find a way to rapidly find the smallest $d$ possible. $\endgroup$ – Tassle Dec 11 '19 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy