GATE IT 2006 | Question: 9

Question

In a binary tree, the number of internal nodes of degree $1$ is $5$, and the number of internal nodes of degree $2$ is $10$. The number of leaf nodes in the binary tree is

• A. $10$
• B. $11$
• C. $12$
• D. $15$

Comments

Although @Kai and @Arjun ji has provided good answer with reference. But before looking at their answer just try considering tree as directed graph.

Answer 1

A node in a binary tree has degree $0, 1$ or $2$. 

Ref: http://faculty.cs.niu.edu/~mcmahon/CS241/Notes/bintree.html

We are given no. of $1$ degree node $= 5$, no. of $2$ degree nodes $= 10$. 

Total no. of edges $= 1*5 + 2*10 = 25$ (In tree degree is for outgoing edges only, and hence each degree corresponds to an edge)

So, total no. of nodes $= 25 + 1 = 26$ (No. of nodes in a tree is $1$ more than no. of edges).

Now, no. of leaf  nodes (nodes with $0$ degree) $= 26 - 5 - 10 = 11$.

Correct Answer: $B$

Comments

Something of note: Degree of a tree is different from degree of a binary tree

---

@Cbirla you are mostly correct but you have to subtract 1 from the final answer.

Reason:Because of root.Consider the case for the root,if it has 1 child,then its degree will be 1 and not 2 according to graph degree definition as root does not have any parent which would contribute 1 extra degree to it.

Likewise if root has 2 children,then its degree will be 2 and not 3.

So now in the formula, 1*(no of degree 0 nodes a.k.a leaves)+2*(no of degree 1 nodes)+3*(no of degree 2 nodes) - 1(for the case of root as we don't know if it is degree 1 or degree 2)=2*(no of edges - 1)  (Degree summation formula for tree)

2*5 + 3*10 + 1*L -1 = 2*(5+10+L-1)

L=11

---

@Silver_Reaper

Perfect answer for same doubt

---

can i say even degree of 1 nodes given leaf nodes depends on degree 2 nodes only can i directly calculate i2+1=10+1=11?is this correct?

Answer 2

In a binary Tree,

no of nodes of degree 2 = no of leaves - 1.

No of nodes of degree 1 do not affect no of leaves !

No of leafs = No of nodes of degree 2 + 1 = 10 + 1 = 11

Comments

@arjun Sir 

@gatecse

A binary tree is a directed graph and hence degree refers to outgoing degree only. We can also consider it as an undirected graph and apply graph rules- but by default it is a directed graph.

 

Why this definition is not using in this:   https://gateoverflow.in/118300/gate2017-1-20 

---

val because in GATE2006 question we are using the definition of a tree defined in DATA STRUCTURES but in GATE2017 we are using the definition of a tree as a graph defined in GRAPH THEORY

NOTE: notice the word 10 vertices.

---

it must be no. of leaves =number of nodes of degree 2 +1 .

Answer 3

$L$ = $T+ 1$

$L$ = number of leaf node

$T$ =  number of nodes with 2 child

$L =10+1$

$L= 11$

Answer 4

In a directed graph indegree of a graph = outdegree

Outdegree = 1*5 + 2*10

Let number of leaves be x

Indegree = x*1 + 14 *1 (all nodes except root have indegree = 1)

Outdegree = indegree

x = 11

Answer 5

Given n1=5, n2= 10, n0=?

Total nodes N= n0+n1+n2

N=n0+15 = Edges -1

Edges= n0*0+n1*1+n2*2

N-1= n1+2n2

15+n0-1= n1+2n2

On solving we get n0= 11

Hence Option B) is correct answer

Answer 6

 

@Shaik Masthan @Arjun Sir can we apply here 

x*1 + 5 *2 + 10*3  -1 = 2* (x+5+10 - 1)     (considering degree as no of incident edges , sum of degree=2 |E| )

x= 39-28  = 11  (ans)                             x is no of leaf nodes.. 1 subtracted as root have only 2 incident edges

It's giving right answer

but is it conceptually correct??

Comments

then ok :)

---

Why you subtracted one...while summing the degrees.

---

actually I also did the same way.

See here degree 1 will be degree 2(1 is the ancestor) as we are considering undirected graph. So 5 nodes have two degree and 10 have 3, but root node would not have ancestor, that is why we are subtracting 1.

check in this image, root has 2 children still its degree is 2(since no ancestor), the other internal node has 2 children, but its degree is 3 since it has an ancestor. This will hold good for all other internal nodes except the root. that is why we subtract 1