in DS edited by
29,952 views
35 votes
35 votes
A binary tree T has $20$ leaves. The number of nodes in T having two children is ______.
in DS edited by
30.0k views

2 Comments

6
6
No. of full nodes(max degree nodes) == No. of leaves - 1
2
2

12 Answers

25 votes
25 votes
Best answer

In A binary tree if there are $N$ leaf nodes then the number of nodes having 2 children will be N-1

$\text{Proof}:$ 

Key idea is find number of edges using Degree and find number of edges using nodes and equate them

Let $l$ be the number of leaf nodes, $D_1$ be the number of nodes with one child and $D_2$ be the number of nodes with two children.

$\text{Sum of Degrees}, D = 1 \times l + 3\times D_2 + 2\times D_1 - 1 \text{(for root)}$

(Root is having one degree less because it is not having a parent) 

$D= l+ 3D_2+ 2D_1 - 1 \qquad \rightarrow (1)$

$\text{Number of edges}, e= \frac{D}{2} $

$\text{Number of nodes}, n = D_2+D_1+l $

A tree with $n$ nodes has $n-1$ edges so,

$\frac{D}{2} = D_2+D_1+l-1\qquad \to(2)$

From $(1)$ and $(2)$

$\frac{l+3D_2+2D_1-1}{2} = D_2+D_1+l-1$

$\implies D_2 = l-1$

So, the number of nodes in $T$ having two children  $= 20-1 = 19$

selected by

4 Comments

Just throwing some things here. 

This proof requires - 

1. Handshaking Lemma (Degree Sum Formula) - It states, sum of degrees of all nodes in a graph is equal to twice the number of edges.  

2. Tree is a connected graph with minimal edges, and as a consequence of this, a graph with $N$ nodes will have $N-1$ edges. 

Now,

Sum of Degrees of all vertices $ = \left(1 \times  l\right) + \left(3 \times  D_2\right) + \left(2 \times  D_1 \right) -1$

where, 

1. $ \left( 1  \times  l \right)$  - No. of leaf nodes is $l$ and leaf nodes have degree $1$. 

2. $\left(3 \times  D_2\right)$ - $D_2$ is no. of nodes with two children. The nodes with $2$ children will have degree of $3$, except for the root. The root will have $2$ children and no parent,hence degree will be $2$.

But we have considered root node in $D_2$, so we assumed degree $3$ for the root node, which is $1$ more than the actual degree $2$. Hence we have to subtract $1$, which is done in the end.

3. $\left(2 \times  D_1\right)$ - Same as above, but here, no conflicts like root. 

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

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

$(\#\ of\ edges )$                          

$n=19$
3
3

@Kushagra गुप्ता 

@Arjun Sir, 

You worte that "In tree, degree is for outgoing edges only, and hence each degree corresponds to an edge​​​​​​​ (https://gateoverflow.in/3548/gate2006-it-9)" then, why you have taken degree of leaf nodes as 1 and not 0?

 

0
0
nice
0
0
36 votes
36 votes
$\mathbf{19}$

In Binary tree If there are $N$ leaf nodes then the number of Nodes having two children will be $N-1$. So in this case answer will be $20-1$, means $19$.
edited by

4 Comments

This question comes once in every three years:p
11
11

@rahul sharma 5  that means 2020 :P

3
3
OK i am ready lol.
0
0
Alas It did’nt come
0
0
27 votes
27 votes

in a binary tree there are 3 types of nodes are possible 1st with 0 child (aka leaf nodes) 2nd, node with 1 child and 3rd, node with 2 children 
suppose no of leaf nodes =k
no ofnodes with 1 child = x
no of nodes with 2 children = y 
so total no of edges = total degree/2
                                = (k+2x+3y-1)/2 = (k+x+y)-1
note - here we are subtracting 1 from  k+2x+3y bcoz of root node.
after solving y = k-1   
so  ans =20-1=19

4 Comments

@Shaik Masthan Sir but in Arjun sir answer only in that link ( the top line) it is given that a node in the binary tree can have degree either 0,1 or 2. There is not a mention of degree 3 node as you have said that node with 2 children have degree 3 ( which is also correct accn to me)

0
0
i am considering it as undirected graph, but sir saying it is directed graph...

first fix one representation, then you can follow it's procedure.

Both approaches gives same answer..

Moreover no need to call me as sir :)
1
1
thanks ..that was a great explaination , my concepts regarding that are clear now..thanks again
1
1
11 votes
11 votes

The total number of nodes in an m-ary tree is given by

n =  m*i +1 where i denotes the number of internal nodes

here in question m=2(binary tree)

so n=2i+1

Also, n = i+ l

where l= number of leaves in a binary tree

Combining above equations we get
2i+1 = i+ l

i + 1 = l

so i = l-1

Hence, number of internal nodes in a binary tree is number of leaves -1.

Answer : 20-1 = 19 Internal nodes or 19 nodes with 2 children are there in this binary tree.

Note : The Equations used above are provided in Kenneth Rosen Graph Theory chapter.

4 Comments

Didn't get you mohit.
Also can you please provide the link of GATE1998 question so that I can relate better what are you trying to say.

0
0

@mohitrai0_0

The above equation holds true if the m-ary tree has 0 or m Children, only.

0
0

In case it is Full-m-ary tree, the formulae N=m*i +1 holds true otherwise not .

0
0
Answer:

Related questions