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

Number of nodes in a tree is one more than the number of edges ...

---

corrected....!!!!!!

---

How can a internal node hav degree 1 ??? According to definition of degree in tree # of edges which r incident on node or # of neighbor nodes ... only leaf nodes can be degree 1 ... internal nodes will be of degree 2 or 3 ... as far i know ... plz anyone clarify it ???

---

@Puja Mishra degree of a node in a tree is the number of children that node has. 

---

Puja Mishra

arjun sir already explained that "In tree degree is for outgoing edges only" ....it means degree of a node is equal to the no of children it have...a node can have either 0 children or 1 children or 2 children...therefore degree can be either 0 or 1 or 2... a skewed tree is an example of internal node having degree one

---

Sorry my bad ....

---

@Arjun Sir,

https://gateoverflow.in/3548/gate2006-it-9?show=14286#a14286

 

Dont we overcount the number of edges by using this relation as some of the edges will be common ?

 

P.S : If definition of "Degree" will be given as "count of neighbors of given node"

---

The confusion is arising because "degree" does not mean the same thing in trees that it means in graphs.

Degree of a node in an undirected graph = Number of edges incident to that node.

Degree of a node in a binary tree = No. of subtrees of that node (0 = no subtree = leaf, 1 = left or right subtree, 2 = both left and right subtrees)

So yes, each "degree" corresponds to an edge in the tree.

---

@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= 25-14   =    11(ans)                             x is no of leaf nodes.. 1 subtracted as root have only 2 incident edges

It's giving right answer

but s it conceptually correct??

---

@ dharmesh7 see this "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. " by arjun sir

---

just drawing an arbitrary tree with "the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10."- we can calculate it.

---

just the idea ...what will its graph look like?

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

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 4

$L$ = $T+ 1$

$L$ = number of leaf node

$T$ =  number of nodes with 2 child

$L =10+1$

$L= 11$