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

minimumnumber of nodes that need to be selected so thateverynode in the tree is at most k nodes 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.