retagged by
23,857 views
42 votes
42 votes
Consider a binary tree T that has $200$ leaf nodes. Then the number of nodes in T that have exactly two children are ______.
retagged by

12 Answers

Best answer
76 votes
76 votes
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$
edited by
27 votes
27 votes

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

=> n-1.

Here n = 200 So answer is 199.

10 votes
10 votes

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 .

7 votes
7 votes

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:

Related questions

36 votes
36 votes
4 answers
1
go_editor asked Feb 14, 2015
9,214 views
Given that hash table $T$ with $25$ slots that stores $2000$ elements, the load factor $a$ for $T$ is _________.
27 votes
27 votes
6 answers
2
go_editor asked Feb 14, 2015
12,852 views
The result evaluating the postfix expression $10 \ 5 + 60 \ 6 / * 8 -$ is $284$$213$$142$$71$
35 votes
35 votes
12 answers
3
go_editor asked Feb 12, 2015
30,018 views
A binary tree T has $20$ leaves. The number of nodes in T having two children is ______.