751 views
a 4-ary tree has either 4 or 0 children,What is the total number of nodes when there are 20 leaf node?
| 751 views
0
@Habibkhan

Ans. Not possible. 20 leaf nodes arrangement for given constraint of 0 or 4 children

I:- no. Of internal nodes

L:- no. Of leaf node

n:- n- ary tree

If u analyze some what you will get following formula:-->>

(n-1) I +1 = L

But for Given question due to ur given constraint of 0 or 4 children

20 leaf nodes are not possible in this arrangment.

If 19 leaf nodes given then we have a solution for this :->> apply on above formula u will get 6 Internal nodes

So total nodes in that case 19+6 = 25 nodes.

selected by
As there is a formulae regarding this:

L=I(n-1)+1

where I=number of internal nodes

L=number of leaf nodes

n=n-ary tree

so in this ques, L=20

20=I(3)+1

I=6.33 can be approximated to 7

now asking for total number of nodes so 20+7

thats 27 nodes

edited
+1
@kirti plz verify ur formula.

I & L should be swapped in ur formula.
+1
yep.. thats my mistake.. it should be L=I(n-1)+1

and then acc to that, ur answer is right.. thanku for correcting me..
0
You are welcome.
ANswer can be 33,37,41.See the image attached 