The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+6 votes
421 views
a 4-ary tree has either 4 or 0 children,What is the total number of nodes when there are 20 leaf node?
asked in Programming by Boss (18.4k points) | 421 views

4 Answers

+12 votes
Best answer
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.
answered by Boss (22.6k points)
selected by
+2 votes
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
answered by Active (3.8k points)
edited by
+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.
0 votes
The total number of nodes = number of Internal nodes (I) + number of leaf nodes (L)

number of leaf nodes (L)=20

number of Internal nodes (I) = [( L-1)/(n-1)] where n = n-ary tree here n=4

I= [(20-1)/(4-1)], so I=6

total number of nodes = 20+6=26
answered by Active (1.2k points)
0 votes

ANswer can be 33,37,41.See the image attached 

answered by (23 points)


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

36,202 questions
43,662 answers
124,113 comments
42,944 users