edited by
30,016 views
35 votes
35 votes
A binary tree T has $20$ leaves. The number of nodes in T having two children is ______.
edited by

12 Answers

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

=> n-1.

Here n = 20 So answer is 19.
1 votes
1 votes

Leaves n0= 20

Total nodes N= n0+n1+n2= 20+n1+n2

Edges= n0*0+n1*1+n2*2 = n1+2*n2.....(I)

Also Edges = N-1 = 19+n1+n2.....(II)

From (I) and (II)

n1+2*n2=19+n1+n2

n2=19. Hence 19 is correct

1 votes
1 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,  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 : 19


In the "Best Selected Answer", They should have used "Number of Neighbors" instead of using the word "Degree" so that students do not confuse. Or they should have defined what they mean by the word "Degree".

Answer:

Related questions

72 votes
72 votes
4 answers
2
62 votes
62 votes
4 answers
3
go_editor asked Feb 12, 2015
16,028 views
Consider a complete binary tree where the left and right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is...