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

3 Answers

+9 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 (14.5k 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.2k 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 (247 points)  
Top Users Jan 2017
  1. Debashish Deka

    7172 Points

  2. Habibkhan

    4696 Points

  3. Vijay Thakur

    4308 Points

  4. sudsho

    4090 Points

  5. saurabh rai

    4024 Points

  6. Arjun

    3292 Points

  7. santhoshdevulapally

    3066 Points

  8. GateSet

    3016 Points

  9. Bikram

    3014 Points

  10. Sushant Gokhale

    2892 Points

Monthly Topper: Rs. 500 gift card

18,838 questions
23,808 answers
51,589 comments
20,148 users