6 votes 6 votes a 4-ary tree has either 4 or 0 children,What is the total number of nodes when there are 20 leaf node? Programming in C tree + – Aboveallplayer asked Sep 3, 2016 Aboveallplayer 2.1k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Shivam Chauhan commented Nov 17, 2016 reply Follow Share @Habibkhan 0 votes 0 votes smsubham commented Feb 13, 2018 reply Follow Share Same question: https://gateoverflow.in/66314/dsa 0 votes 0 votes Please log in or register to add a comment.
Best answer 17 votes 17 votes 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. Rajesh Pradhan answered Sep 4, 2016 • selected Sep 4, 2016 by ManojK Rajesh Pradhan comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 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 kirti singh answered Sep 3, 2016 • edited Nov 19, 2016 by kirti singh kirti singh comment Share Follow See all 3 Comments See all 3 3 Comments reply Rajesh Pradhan commented Sep 4, 2016 reply Follow Share @kirti plz verify ur formula. I & L should be swapped in ur formula. 1 votes 1 votes kirti singh commented Sep 4, 2016 reply Follow Share 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.. 1 votes 1 votes Rajesh Pradhan commented Sep 4, 2016 reply Follow Share You are welcome. 0 votes 0 votes Please log in or register to add a comment.
0 votes 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 Neeraj7375 answered Nov 5, 2016 Neeraj7375 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes ANswer can be 33,37,41.See the image attached Anubhav Kaushik answered Nov 25, 2017 Anubhav Kaushik comment Share Follow See all 0 reply Please log in or register to add a comment.