GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
179 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 Veteran (18.3k points)   | 179 views

3 Answers

+10 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 Veteran (16.8k points)  
selected by
+1 vote
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 Loyal (3.3k points)  
edited by
@kirti plz verify ur formula.

I & L should be swapped in ur formula.
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..
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 (355 points)  


Top Users May 2017
  1. akash.dinkar12

    3338 Points

  2. pawan kumarln

    2066 Points

  3. Bikram

    1922 Points

  4. sh!va

    1672 Points

  5. Arjun

    1614 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1174 Points

  8. Angkit

    1056 Points

  9. LeenSharma

    1018 Points

  10. Arunav Khare

    758 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    1008 Points

  2. pawan kumarln

    692 Points

  3. Arnab Bhadra

    632 Points

  4. Arjun

    342 Points

  5. bharti

    328 Points


22,888 questions
29,193 answers
65,292 comments
27,691 users