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

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.
by Boss (23.4k 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
by Active (3.6k 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
by Active (1.3k points)
0 votes

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

by (23 points)

Related questions

+3 votes
0 answers
6
0 votes
0 answers
7
asked Sep 28, 2018 in Programming by Vaishnavi01 (143 points) | 85 views
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
49,807 questions
54,713 answers
189,263 comments
79,706 users