Minimum Camera Required :
Difficulty Level : Medium
Submissions : 290
Asked In :
Marks :30
: 13 | : 0
Given a binary tree rooted at $$$1$$$, you need to place cameras on some nodes such that every node in the tree could be under surveillance.
Given that each camera will provide surveillance to an immediate neighbor in the tree.
You need to find the minimum number of nodes such that the total number of cameras to be installed is minimum.
The first line contains an integer $$$n$$$, the number of nodes in the tree. The next $$$n$$$ lines contain two space-separated integers $$$x$$$ and $$$y$$$ denoting an edge between $$$x$$$ and $$$y$$$.$$$(1 \le n \le 10^3).$$$ It is guaranteed that the tree is a binary tree.
Output minimum number of nodes on which cameras should be installed such that the total number of cameras to be installed is minimum.
5 1 2 1 5 2 3 3 4
2
3 1 2 1 3
1
4 1 2 2 3 3 4
2
11 1 2 2 3 2 4 3 5 3 6 4 7 4 8 1 9 9 10 9 11
3
