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

Number of leaf nodes (L) = Number of degree 2 nodes (N2​) + 1

holds true only for full binary trees, not for arbitrary binary trees.

proof:- 

in a full binary tree, all nodes are either having two children or 0 children.

let n be the total no of nodes, L be the no.of leaf nodes and N2 be the internal nodes or nodes having two children.

n = L + N2

now, in a tree no of edges = n-1 

or,   n -1 =  2 (N2)  + L 

on simplifying we get, L=N2​+1

no of leaf nodes = no. of internal nodes (having two children )  + 1.

---

In a binary tree, suppose we have 7 nodes in total and 4 leaf nodes.
That means the remaining 3 nodes are internal nodes.

Since each internal node has exactly 2 children, the structure satisfies the binary tree property.

From this, we can conclude the relation:

Number of internal nodes=Number of leaves−1
so ans for this   
200-1=199

---

adding 1 node internal node having 2 childrens increases the overall number of leaf nodes by 1 in a binary tree [you can draw the tree and notice it by yourself easily ] 

 

if i add "N" nodes internal nodes of degree 2 in a binary tree , then number of leaf nodes will be N+1 

 

here, N+1 = 200, then N  = 199 

 

NOTE --> adding a node with degree 1 in a binary tree does not changes # of leaf nodes as - 

previously, assume you have "x" leaf nodes , 

you added 1 node with degree 1, so that leaf become internal with degree 1 child and that child node became a leaf node 

overall leaf node = x + (-1+1) = x only 

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

$\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

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.

 

Answer 4

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 5

199 nodes with degree 2.

Comments

ok

---

answer is 199

Answer 6

Answer is: 199

Because, In Binary Tree, number of leaf nodes is always one more than nodes with two children.

L=T+1

where, L=Number of leaf nodes

          T=Number of internal nodes with two childrens