2
$\begingroup$

I received this problem on an exam a few months ago, and have kept thinking about how to solve it with no luck.

Given a binary tree where each node in the tree can either be selected or unselected, implement a function k_away() which returns the minimum number of nodes that need to be selected so that every node in the tree is at most k nodes away from a selected node. Example of k_away() selecting 2 nodes (denoted by the darkened circles) so that every node is at most 3 away from a selected node The above image shows an example of k_away() selecting 2 nodes (denoted by the darkened circles) so that every node is now at most 3 away from a selected node.

So, the nodes simply contain a pointer to the left child, a pointer to the right child, and a boolean marking it as selected or not:

struct Node {
    Node *left;
    Node *right;
    bool selected = false; // starts out false
};

The problem specifies a constraint of having a time complexity of O(n) and an auxiliary space complexity of O(n).

What I've thought of so far:

  • It seems like there are 2^n potential solutions (if I can choose to either select or not select every node and there are 2 of them), so brute force is a bad idea
  • I've searched around for similar problems and the closest thing I can find is the Dominating Set problem which seems... impossible to solve at this moment in polynomial time. I doubt this problem was given as an impossible problem.
  • Running DFS to get to the leaf nodes, then counting height as recursion unrolls. Every k away, marking the node as selected. This seems to work on small test cases, but does not return the minimum number away.
  • Running BFS on the root node to find all nodes k away while using another data structure to mark all visited nodes as 'covered', and then recursively running the BFS on each k-away node. This also seems to work on small test cases, but again doesn't return the minimum number away.
$\endgroup$
6
  • $\begingroup$ The problem statement regrettably does not explicitly specify what k nodes away means, not even one. $\endgroup$ – greybeard Aug 15 '20 at 6:55
  • 1
    $\begingroup$ 1) "I doubt this problem was given as an impossible problem." It's common that problems on trees are usually simpler than on general graphs. This is the case here. 2) The keywords to look for are "dynamic programming on trees". After you understand the general idea, you'll be able to come up with a simple greedy solution. Hint: essentially, it'll be a DFS (starting from the root) which selects the nodes from bottom-up. $\endgroup$ – Dmitry Aug 15 '20 at 7:30
  • $\begingroup$ @greybeard I can attach a diagram provided as an example, but it's essentially distance = counting the # of edges between two nodes on the shortest path $\endgroup$ – njwcc Aug 15 '20 at 16:59
  • $\begingroup$ @Dmitry Thanks for the response, I see what you meant when I did some more research (that some np-hard problems are "easy" for trees). With your hint, does that mean my bullet point regarding DFS was on the right track? I searched up a bit re: dp on trees, so would I be asking a question like "does including or excluding the current node minimize how many nodes I need to select" for each node on my way from bottom to top? $\endgroup$ – njwcc Aug 15 '20 at 16:59
  • $\begingroup$ I don't understand what exactly you mean there, but it seems this way. As I understand, you want to select the nodes from top to bottom, but it won't work: you should select them from bottom to top. For DP the question would be like "for each subtree and for each $k'$, find the minimum number of selected nodes in that tree so that the maximum distance from root of the subtree to a node in the subtree which is not at distance $k$ of some selected node is $k'$". For the greedy strategy you just have to notice that decisions when to select a node are pretty simple. $\endgroup$ – Dmitry Aug 15 '20 at 17:22

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.