Here is an example tree:enter image description here

Each node has either $0$ or $4$ nodes. The values $v(n)$ of the node $n$ is given by $v(n) = v(\operatorname{parent}(n)) + k(n)$, where $k(n)\in \{2, 2.5, 8, 50\}$, such that a parent has childs of each value. Find the $K$ least nodes in a given tree (always ignore the root node). For our example tree, we get

$K = 4$, values are: $2, 2.5, 4, 4.5$

$K = 6$, values are: $2, 2.5, 4, 4.5, 5, 8$

Parsing all the nodes and sorting is a straightforward solution. But is there a more optimum solution?

In particular, I tried to

  • parse the tree fully in a recursive fashion.
  • put each node into an array as we parse.
  • sort the array in increasing order.
  • take the first $K$ values.

If there are $N$ nodes in total, then this solution will be of the order of $O(N\log N)$.

Is there a more efficient method?

  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Jan 17 '18 at 17:43
  • $\begingroup$ @Discretelizard Yes a node can have zero or exactly four nodes. Which is why the least K values can differ. $\endgroup$ – aqs Jan 18 '18 at 9:20
  • $\begingroup$ @D.W. I have updated the question with what I tried, which is much more readable. Please ignore the above comment. Thanks! $\endgroup$ – aqs Jan 18 '18 at 9:29
  • $\begingroup$ Your question is: "Is there a more efficient method than X?" When I asked what you tried, your response was "I tried X". So maybe I should rephrase my comments. What I'm trying to say is that you are posting here a copy of an exercise-style question, and appear to be asking us to solve it for you. However, that's not really going to help you. The purpose of exercises is to give you the opportunity to practice, and the benefit comes from you trying to solve it. So, I encourage you to keep trying. $\endgroup$ – D.W. Jan 18 '18 at 18:43
  • $\begingroup$ Questions where you ask us to solve an exercise for you typically aren't a good fit here. If you have a specific question about a specific aspect of the exercise (e.g., "I think dynamic programming is possible, and I made some progress, but I got stuck at this specific step, how do I make that step work?") it might be suitable. But better to read the link that I shared, and see how you can use that to make your question a better fit for our site format. $\endgroup$ – D.W. Jan 18 '18 at 18:44

Your Answer

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

Browse other questions tagged or ask your own question.