The Gateway to Computer Science Excellence
+3 votes
Consider a binary tree T that has 150 leaf nodes. Then the number of TOTAL nodes in T that have exactly two children are ______.
in DS by Loyal | 230 views
149 Total number of the Internal nodes which is having exactly two children.

And there are total 299 nodes.

In Binary tree,

It is easy by just observing, But for n-ary tree try to apply this logic,

1 Internal node = n children

2 internal nodes = n - 1 children + n children [why this, because out of above n leaves we are making one non leaf, then again n children for that non leaf]

3 internal nodes = (2n -1) -1 + n = 3n -2 children 

So pattern is 

X non leaves = Xn - (X-1) leafs

now in our case Xn - (X-1) = 150

Hence X = 149.

In binary tree it is easy to solve by observing 2-3 small trees, leaf - 1= internal. But hope this helps for complex trees. :)

All the internal nodes in Binary tree have exactly 2 childrens

Let $N$ be total no of nodes, $I$ be total internal nodes and $L$ are no of leaves Binary tree then


Also $N=I+L$



Given $ L=150$, $I=150-1=149$

@Ashwani : it is no where given that 

All the internal nodes in Binary tree have exactly 2 childrens

So your formula $N=2 \times I +1$may not hold always true .


It should be "Total no of nodes in m-ary tree is, $ n = m*i + 1$" , right?
@ashwani your formula will hold iff every node have either $0$ children or $m$ children can try to take $m=2$ and include one node having $1$ child and then calculate $n$ , you will get incorrect result .

Yes that I know, I got that it is true for complete Binary tree but it also not given that it is complete or every internal node have 0 or 2 children.

Correct way to do this:

# of nodes with 0 children (leaves) = 150

# of nodes with 1 children = p

# of nodes with 2 children = q

Total nodes = 150+p+q

total edges = 149+p+q

2* total edges = Sum of degree

2*(149+p+q) = 150*1+p*2+q*3 -1

On solving q = 149
yes now its correct

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,215 questions
60,016 answers
94,703 users