GATE CSE 2015 | Set 2 | Question: 10

Question

A binary tree T has $20$ leaves. The number of nodes in T having two children is ______.

Comments

Similar question

https://gateoverflow.in/8428/gate2015-3_25

---

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

---

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.

---

@usher . The derivation is NOT correct.
n-1 = 2(N2) + L
(L + N2) - 1 = 2(N2) + L

L cancels out according to your derivation.

 

Let:

• n₀ = number of leaf nodes (degree 0) — contributes 0 edges
• n₁ = number of degree-1 nodes — contributes 1 edge  
• n₂ = number of degree-2 nodes — contributes 2 edges

 

Total number of nodes in the binary tree:

\[
N = n_0 + n_1 + n_2
\]

In any tree, number of edges = N − 1.

Hence, counting edges by degree contribution:

\[
N - 1 = (n_0 \cdot 0) + (n_1 \cdot 1) + (n_2 \cdot 2)
\]

Substitute \(N = n_0 + n_1 + n_2\):

\[
n_0 + n_1 + n_2 - 1 = n_1 + 2n_2
\]

Cancel \(n_1\) from both sides:

\[
n_0 + n_2 - 1 = 2n_2
\]

\[
n_0 = n_2 + 1
\]

Therefore, for any binary tree:
\[
\boxed{n_0 = n_2 + 1}
\]
 

Answer 1

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$

Comments

Nice Explanation.

 

---

nice proof, well explained

---

https://gateoverflow.in/3390/gate-it-2008-question-76

similar concept question, this concept is asked a lot in gate, like every alternate year or so

Answer 2

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

Comments

OK i am ready lol.

---

Alas It did’nt come

---

2026 ?

Answer 3

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

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)

---

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 :)

---

thanks ..that was a great explaination , my concepts regarding that are clear now..thanks again

Answer 4

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.

Comments

@mohitrai0_0

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

---

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

---

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

I think this statement is wrong 

The correct statement will be

Number of nodes having 2 children in a binary tree is equal to number of leaf nodes - 1

Answer 5

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

=> n-1.

Here n = 20 So answer is 19.

Answer 6

20-1 = 19 ans