GATE CSE 2015 Set 3 | Question: 25

Question

Consider a binary tree T that has $200$ leaf nodes. Then the number of nodes in T that have exactly two children are ______.

Comments

Check: https://gateoverflow.in/8059/gate2015-2-10

Answer 1

Let number of nodes with exactly two children be $x$, and with exactly one children be $y$.

Total degree $= 200 + 3x + 2y - 1$ (As all nodes with $2$ children have degree $3$ except the root)

No. of nodes$ = x + y + 200$

No. of edges $= $Total degree/$2 = (200 + 3x + 2y - 1)/2$    [Handshaking Theorem]

No. of edges in a tree $=$ No. of nodes$ - 1$

So, $(200 + 3x + 2y -1) = 2x +2y + 400 - 2$

$x = 199$

Comments

@Arjun Sir

Binary tree is by default directed, so degree of a node is actually the outdegree. Then, why this ? As nodes with 2 children have out degree 2.

As all nodes with 2 children have degree 3

---

We can solve either way rt? I considered it like an undirected graph.

---

ohh yes !! Graph rules will be the same . Missed that .

---

@Arjun Sir

if I do No of leaves=No of internal node+1

then same answer

We can apply this formula as well,rt?

---

then what about nodes with 1 child?

---

Does the answer assume that Root will have 2 children? I think if root is havong one child then first equaltion  will not hold

---

As all nodes with 2 children have degree 3 except the root

Arjun Sir, root might not have 2 children i.e. it may have degree 1 or 2. So while calculating the total degree why do we assume that the leaf nodes are the only nodes having degree=1 and compute like (200*1 + 3*x + 2*y-1)?  

---

a root cannot be a leaf

---

if root has 1 child quation will be

$\left ( x+y+200+1 \right )-1=\left ( 200+3x+2y+1 \right )/2$

Still x=199

---

Similarly if we do root with degree 2 separately

$\left ( 200+3x+2y+2 \right )/2=x+y+200$

x=198

then taking root it will be 198+1=199

right?

---

srestha yes . I just wanted to know whether there is any generalized formula which considers cases for root having degree 1 or 2. The answer would come same for both as you have shown. Thank you

---

yes no generalized formula

just eliminate root node first and then add it

---

tricky question, right?

---

Hehe yeah right :P

---

Actually other than leaf node, we cannot say all other nodes have 2 child, though it is a binary tree

That makes question to think more

---

if we say that the root has only one child then

the degree is 200+(2y-1)+3x

if we say that the root has 2children  then

the degree is 200+2y+(3x-1) both the cases the formula will remain the same.

---

$\underbrace{\dfrac{200+(n-1)\times 3+1\times 2}{2}}=\underbrace{200+n-1}$

$handshaking-lemma$           $\#\ of\ edges\ in\ a\ tree$

$(\#\ of\ edges )$                          

$n=199$

---

Degree of a vertex = No of edges connected to the vertex

---

Kind of a difficult qsn. This equation with 2 unknowns and one of them gets eliminated in the end will never strike first in exam .

Answer 2

The general formula for a Binary tree having two children with n leaves is

=> n-1.

Here n = 200 So answer is 199.

Comments

General formula-

$L=(n-1)*i +1$

Where i is number of internal nodes and L is no. of leaves.

(for n-ary tree having 0 or n children to each node.)

Answer 3

Let N(n) be the no of leaves in a binary tree which has n internal nodes of degree 2 

Now consider the base condition to be N(1)=2 i.e. a BT where I have only one root node with 2 leaves , now each time u will make an internal node u will start with this structure only .

Say in this structure only where u have 1 root and 2 leaves , u make one of the leaf node as an internal node ,now this internal node would give rise to 2 leaves more considering the fact that I am making an internal node having  2 children ,since if u add an internal node of 1 children ,it won't ever effect the no of leaves in the tree .

So the key point is that at each instant as  we increase the no of internal node by 1 ,I do this by making one of the leaf node as my internal node and then this new node formed would again give rise to 2 nodes as I mentioned above , so reccurence relation can be formed like

N(n)=N(n-1)-1+2 , I did -1 since from previous no of leaf nodes , we are making one of the leaf nodes as an internal node of children 2, now after it becomes internal node ,it would give rise to 2 leaf nodes , so added 2 to it since we have to count the no of leaf nodes ,

So solve this N(n)=N(n-1)+1 , with base condition as N(1)=2 , u will get the answer as n+1 as no of leaves , now note that I considered n to be the no of nodes of degree 2 , so this implies that if I have no of leaves to be n+1 , no of nodes of 2 children are n , so that implies If I have n leaf nodes , no of internal nodes of children 2 would be n-1 .

Comments

Excellent Solution.
Thanks @Radha !!!

Answer 4

The answer is already given in the Best Selected Answer. I just want to provide one more way to solve this question. 

Many students are confused about what should be the definition of degree for Trees. 

When Tree is considered to be an undirected graph, then degree of a node is the number of neighbors of that node. 

But when Tree is considered to be Rooted tree then definition of Degree is different. Generally, if nothing is mentioned,  For a rooted tree, the definition of Degree of node is the number of children of that node.

(When you terms like "Child, Children, Root, Leaf, Leaves, Internal nodes, binary tree" then think of that tree as Rooted tree and in that case, if Degree definition is explicitly Not given, then consider the above definition for Degree )

 

So, in a binary tree, there are zero degree, one degree, two degree vertices possible.

Let number of leaves (leaves are 0-degree vertices) = $L$,

Number of one degree vertices = $D_1$,

Number of two degree vertices = $D_2$.

For this definition of Degree, we have : 

Number of edges = Sum of degrees

$L + D_1 + D_2 -1 = 2D_2 + D_1 $
$L = D_2 + 1$

$D_2 = L-1$

Answer : 199

---

In the "Best Selected Answer", Arjun sir should have used "Number of Neighbors" instead of using the word "Degree" so that students do not get confused. But they have defined what they mean by the word "Degree" so it shouldn't create confusion.