Question $1$

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. Your 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.

$($a$)$ Develop an algorithm to find the minimum number of security guards required for

any given museum structured as a standard binary tree. Analyze the worst$-$case

time and space complexity of your algorithm.

Hint: Consider using DFS $($for a bottom$-$up traversal of the rooms$).$