MadeEasy Subject Test: Programming & DS - Trees

Question

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

Comments

I cannot imagine how a 4-ary tree with 20 leaves is possible.

---

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.

---

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?

Answer 1

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

Answer 2

L=(K-1)*i+1

k=4

L=20

i=(20-1)/3

total node = internal + leaf nodes

N=i+l

N=20+7

Answer 3

The above binary tree is not possible with above condition. However If the total number of leaf nodes were 19 instead of 20 then internal nodes would have been 6. And hence total number of nodes would have been

Internal + leaf node = 6+19=25

Answer 4

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…