edited by
16,776 views
42 votes
42 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.

$n_3$ can be expressed as

  1. $n_1 + n_2 - 1$  
  2. $n_1 -2$
  3. $[((n_1 + n_2)/2)]$
  4. $n_2 - 1$
edited by

5 Answers

Best answer
77 votes
77 votes

Given definition of degree: no of neighbours of a node.

total nodes $= n = n_1 + n_2 + n_3$

Apply handshaking lemma:

Sum of degrees $= 2 * $no of edges

$1 * n_1 + 2 * n_2 + 3 * n_3  =  2 (n-1)$

Total number of edges in graph will always be $(n_1+n_2+n_3-1)$.

$1 * n_1 + 2 * n_2 + 3 * n_3  =  2 (n_1+n_2+n_3-1)$

$n_1 + 2 n_2 + 3 n_3  =  2 n_1 + 2 n_2 + 2 n_3 - 2$

$n_3 = n_1 - 2$   Option B

edited by
24 votes
24 votes

No. of node in binary with  1 degree i.e. leaf node

2 degree i.e. only root note

node with 3 degree i.e. internal node except root (degree 2)

so number of degree 3 vertices are calculated = interms of internal node -1

internal node = leaf node -1 i.e. n1-1

since from internal node root is 2 degree vertex so removes it 

So no. of 3 degree vertices are = n1-1-1= n1-2

3 votes
3 votes

Option b is right.

 

Answer:

Related questions

32 votes
32 votes
2 answers
3
Ishrat Jahan asked Oct 29, 2014
12,455 views
How many distinct BSTs can be constructed with $3$ distinct keys?$4$$5$$6$$9$