GATE IT 2008 | Question: 76

Question

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

• A. $n_1 + n_2 - 1$  
• B. $n_1 -2$
• C. $[((n_1 + n_2)/2)]$
• D. $n_2 - 1$

Comments

just by taking example we can check all options 

https://gateoverflow.in/3390/gate-it-2008-question-76?show=3394#a3394

---

neighbours =

you can take it as the total number of incoming + outgoing edges in a node

---

I got confused with the term neighbours here...Knowing this information makes the question very easy

Answer 1

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

Comments

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

Shouldn't we subtract $1$ from LHS for root ? $\implies$ NO

Because we are not considering the no. of nodes with child 0, 1 or 2 which is considered in this ANSWER

---

easiest way to understand thanks

---

If Someone have doubt , how degree three is possible in binary tree, then focus on this line -

"The degree of a node is defined as the number of its neighbours"

Degree is not no. of child, it's a no. of neighbour.

Answer 2

assume the above tree so value of n1 is 3 n2 =1 n3 =1 check with options now u vil get option B as correct

Comments

what does it means : value of n1 ?

---

N1 is leaf node.

Answer 3

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

Comments

u r saying, only root node has degree 2,

now suppose in the above drawn tree, i add a left child, to node v3, now v3 also has degree 2, so overall, now there'll be  2 nodes with degree 2..

---

A binary tree with n>1 nodes has n1,n2 and n3 nodes of degree one,two and three respectively,

the total sum total of  degrees= n1*1+n2*2+n3*3

now by formula ,

total no of degrees/2= no of edges in a tree

in this question no of total edges=no of nodes-1

now, total edges=(n1+n2+n3)-1

by formula,

(n1*1+n2*2+n3*3)/2=n1+n2+n3-1

n1+2*n2+3*n3=2n1+2n2+2n3-2

so n3=n1-2     ......................................(b) ans

---

if L=I+1 is true only for full binary tree or for all Binary tree?

where L=Number of leaves nodes

I= number of Internal nodes

---

full

---

Then for given the binary tree in above question why you used this

internal node = leaf node -1

---

if u see clearly i mention there internal node( i am using internal node are those whose degree is 3). apply on any graph then u get it.

like in below graph only one vertex has degree 3 ( i assume only that as internal node)

---

node with 2 degree in a Binary tree will not be only root node,there may be more than root node.

---

With the no. of fill in the blank questions increasing these days, I think this solution by @babal is the correct way to go.

---

@reena can u show an example ??

---

@Puja Remove v5 in the above diagram.

---

Actually this relation doesn't consider nodes having degree as 2 i.e. n₂. (in case tree is not a complete binary tree) . Its clear from below example, here n₃=2, n₂=4, n₁=4, and n₃=n₁-2=2

So we can conclude that it only determines nodes having degree 3 if we are provided leaf nodes count ( as per definition of degree given)

Please correct me if I am wrong.

---

now, total edges=(n1+n2+n3)-1

can you explain it how it derive?

though it may be trivial question but i am not getting it

---

@Prashant.

why only full.I thibk it is applicable for all binary trees.Please clarify

---

@Prashant. the defination you have told about the degree is only specific to question, right!
so In general.
In graph(undirected) degree of a node considered as the total number of edges connected to that perticular node.
but if the graph is undirected than the degree of a node is considered as the arrow going out from that perticular node.
So the BINARY tree is also a directed graph hence degree of a vertex in tree is arrow going from the node.
now. 

DEGREE OF ROOT NODE – 2 OR 1

DEGREE OF LEAF NODE – 0 

 

---

must read comments by @Madhab and @meghna

Answer 4

Option b is right.

 

Comments

Degree is define in question

---

Raj

Read the question carefully .

n3 is the number of 3 degree node .on graph number of 3 degree node is 2 hence n3=2

---

@Abhishek

I got it.

Thanks!.

Answer 5

this question can be done without the help of number of edges . 

We know that :

number of internal nodes with 2 children (I) =  number of leaf nodes (L) - 1

n1 is node with degree 1 -- they are leaf nodes [h,e,f,g]

n2 is node with degree 2 -- they are nodes with 1 children and the root node [a ,d]

n3 is node with degree 3 -- they are internal nodes with two children but it does not include the root node because root node has degree 2 [b,c]

so , 

n3  = internal node - 1  {this 1 excludes the root node }

n3 = (leaf nodes - 1) - 1 

n3 = n1 - 2

hence option B is correct . 

 

 

Comments

The best answer here....

Answer 6

n1 = degree 1 node , n2 =degree 2 nodes , n3= degree 3 nodes
Here degree means no of neighbours

Now confusion is what to consider as neighbours ? Is no of neighbours  are no of childs or normal degree right ?
So if it no of childs we consider it means we have treated binary tree as directed so n3 = degree 3 nodes means we are considering
3 childs which is not possible in BT

So , here binary tree considered as Undirected tree
Now we can apply the normal procedure
Sum of degree = 2( no of edges )

Note : Here if root have only 1 child it means 1 degree right so it has been covered by n1 nodes or if root has 2 childs then it means 2 degree right so it has been covered by n2 nodes

So no need to worry about how to handle the root

Now use the formula
Edges = total nodes (Vertices ) -1
n1*1 + n2*2+ n3*3 = 2( n1+n2+n3 -1 )
n1 + 2n2 + 3n3 = 2n1+2n2+2n3-2

n3=n1-2

If in case any doubt regarding any Pyqs like this
Tag Me will help to solve it