DS TREES

Question

Consider a binary tree T that has 150 leaf nodes. Then the number of TOTAL nodes in T that have exactly two children are ______.

Comments

149!

---

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

$N=2*I+1$

Also $N=I+L$

$I+L=2*I+1$

$I=L-1$

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

---

https://gateoverflow.in/2604/gate1995_1-17

@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 .

---

@sourav

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 ..you can try to take $m=2$ and include one node having $1$ child and then calculate $n$ , you will get incorrect result .

---

@Sourav

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

---

https://gateoverflow.in/2604/gate1995_1-17

---

Thanks