edited by
14,596 views
61 votes
61 votes

A binary tree with $n > 1$ nodes has $n_1$, $n_2$ and $n_3$ nodes of degree one, two and three respec­tively. The degree of a node is defined as the number of its neighbours.

Starting with the above tree, while there remains a node $v$ of degree two in the tree, add an edge between the two neighbours of $v$ and then remove $v$ from the tree. How many edges will remain at the end of the process?

  1. $2 * n_1- 3$
  2. $n_2 + 2 * n_1 - 2$
  3. $n_3 - n_2$
  4. $n_2+ n_1- 2$
edited by

5 Answers

Best answer
89 votes
89 votes
Initially, $n_1*1+n_2*2+n_3*3=2(n_1+n_2+n_3-1)   \implies  n_3=n_1-2$

Now we have removed all $2$ degree nodes, so number of edges in final graph is $n_1+n_3-1.$

Put $n_3=n_1-2,$ we get

Number of edges $=2*n_1-3$
selected by
46 votes
46 votes

From the above tree, we will get the tree below 

Now, check with the options we will get $(A)$ as the answer.

edited by
5 votes
5 votes
Another method:

Sum of degrees: n1+2*n2+3*n3

now number of edges =  (n1+2*n2+3*n3)/2

now all 2 degree nodes were removed ... by doing this degrees of remaining vertices will not affect. as we are forming an edge between neighbouring vertices.

hence number of edges= (n1+2*n2+3*n3-2*n2)/2 =  (n1+3*n3)/2

now replace n3 = n1-2 (from first linked question)

=>(n1+3(n1-2)) / 2

=>2n1-3
1 votes
1 votes
May be we can eliminate b, c ,d .

By applying procedure given in a question, there will not be any node with degree 2 left  i.e  $n_2$ , only option A doesn't have   $n_2$ .
Answer:

Related questions

42 votes
42 votes
5 answers
1
Ishrat Jahan asked Oct 29, 2014
16,776 views
A binary tree with $n 1$ nodes has $n_1$, $n_2$ and $n_3$ nodes of degree one, two and three respec­tively. The degree of a node is defined as the number of its neighbo...
32 votes
32 votes
2 answers
3
Ishrat Jahan asked Oct 29, 2014
12,456 views
How many distinct BSTs can be constructed with $3$ distinct keys?$4$$5$$6$$9$