The Gateway to Computer Science Excellence
+1 vote
135 views
A 4-ary tree,i.e. each node has either 0 or 4 children tree has 20 leaf nodes. Then the total number of nodes in the tree are ____.
in DS by
edited by | 135 views
0
I cannot imagine how a 4-ary tree with 20 leaves is possible.
0
Not possible, i guess there is something wrong with question.

If we try to calculate no of internal nodes

N= 4*I + 1 = I + 20

Internal nodes are coming as 6.33 which is not possible.

19 leaf nodes can be possible with 6 internal nodes in total 25 nodes.
0
Firstly the tree isn't possible if we take the theoretical perception using the formula they have provided in that they're calculating the answer to be 26.3 &  they're taking upper bound of it, just not getting why?

2 Answers

+1 vote

          /                      Root                               \                          |

        /                   /                  \                         \                         |

     N1                 N2                 N3                    N4                       N6 

/            \      /           \        /              \          /               \          /              \

1  2  3  4      5  6  7    8      9  10  11  12        13  14  15  16        17  18  19  20

from above scenario we can conclude that tree is not possible with given data...

by
+1 vote
L=(K-1)*i+1

k=4

L=20

i=(20-1)/3

total node = internal + leaf nodes

N=i+l

N=20+7
by
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,345 questions
60,495 answers
201,848 comments
95,307 users