Find the minimum number of switches to be turned on for illuminating the binary tree
<p>Consider a binary tree like:</p>

<p><a href="https://i.stack.imgur.com/ymckC.jpg" rel="nofollow"><img src="https://i.stack.imgur.com/ymckC.jpg" alt="enter image description here"></a></p>

<p>Think of the nodes as switches, which are initially <code>OFF</code> and the edges between nodes as tube lights (not glowing initially). When we switch on a particular node, then all the edges(tube lights) connected to that node glow. Find the minimum number of switches that need to be turned <code>ON</code> for the whole binary tree to glow.</p>

<p>For example, if I switch on <code>2,3,4 and 9</code> or <code>2,3,8,9</code> then all the tube lights glow. So, the answer is <code>4</code> [see the diagram]</p>

<p>I was asked about this question in an interview. Can anyone help me with the algorithm/pseudocode? No need for working code.</p>

<p>For programmers and coders, think that the input is like:</p>

<p><code>n</code>: the number of edges given</p>

<p>Then <code>n</code> lines follow in the form <code>x y</code> where <code>x</code> and <code>y</code> are two endpoints of the edge.</p>

<p>According to the diagram above, the input will be:</p>

<pre><code>10
1 2
1 3
2 5
...
</code></pre>

<p>Till now, I have figured out a few cases like: <strong>I never need to illuminate the leaf nodes</strong></p>

<p>Is a simple recursive solution present based on the above fact?</p>

<p><strong>Edit:</strong> Will the algorithm change if only the <code>Root</code> of the tree is given as <code>input</code> [Assume the tree is represented as a linked list] ??</p>