# DFS to assign guards to nodes in a tree structure

Consider a uniquely designed museum where rooms are arranged in a tree structure. Each room can have up to two child rooms connected by a path. The task is to develop an algorithm to place a minimum number of security guards so that the entire museum is guarded. A guard placed in a room can guard that room, its parent room, and its direct child rooms. It is a standard binary tree, and using DFS for bottom-up traversal is expected. Worst case time and space complexity is to be expressed.

I thought traversing as post order and looking whether a node has a parent and having at least one child to assign a guard to it, but it also adds extra guards. Should we also check if a node is guarded etc or is there a better way without it since we traverse bottom to up?

This looks like the dominating set problem, but in a tree.

If the tree has two nodes or more, note that it is never interesting to put a guard in a leaf, because putting the guard in its parent will cover more rooms. Conversely, since you need a guard to check the leaf room, you need to put a guard either in the leaf or in its parent.

This gives the idea of an algorithm: using a DFS traversal in post-order, for each node, if it is uncovered, put a guard in its parent. The idea is that after putting a guard in the parent of a leaf (as stated above) and deleting covered nodes, this creates new leaves and you can apply it recursively (note that this can disconnect the tree, but it is not a problem).

• when do I delete them and will I do a search from beginning? Or why do I delete them, since I won't go back to that node.
– mark
Mar 16 at 16:08
• Sorry, I didn't understand your comment. Mar 16 at 17:59
• May you elaborate further, after deleting the nodes how do I search recursively?
– mark
Mar 16 at 20:27
• That's up to you to make it work, I already gave the idea. Mar 16 at 21:14