The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
DSA
+6
votes
421
views
a 4ary tree has either 4 or 0 children,What is the total number of nodes when there are 20 leaf node?
trees
asked
Sep 4, 2016
in
Programming
by
Aboveallplayer
Boss
(
18.4k
points)

421
views
Facebook
Google+
Twitter
answer
comment
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
4
Answers
+12
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:>>
(n1) 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
Sep 4, 2016
by
Rajesh Pradhan
Boss
(
22.6k
points)
selected
Sep 4, 2016
by
ManojK
comment
Please
log in
or
register
to add a comment.
+2
votes
As there is a formulae regarding this:
L=I(n1)+1
where I=number of internal nodes
L=number of leaf nodes
n=nary 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
Sep 4, 2016
by
kirti singh
Active
(
3.8k
points)
edited
Nov 19, 2016
by
kirti singh
comment
+1
@kirti plz verify ur formula.
I & L should be swapped in ur formula.
+1
yep.. thats my mistake.. it should be L=I(n1)+1
and then acc to that, ur answer is right.. thanku for correcting me..
0
You are welcome.
Please
log in
or
register
to add a comment.
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) = [( L1)/(n1)] where n = nary tree here n=4
I= [(201)/(41)], so I=6
total number of nodes = 20+6=26
answered
Nov 5, 2016
by
Neeraj7375
Active
(
1.2k
points)
comment
Please
log in
or
register
to add a comment.
0
votes
ANswer can be 33,37,41.See the image attached
answered
Nov 25, 2017
by
Anubhav Kaushik
(
23
points)
comment
Please
log in
or
register
to add a comment.
← Prev. Qn. in Sub.
Next Qn. in Sub. →
← Prev.
Next →
Related questions
+3
votes
0
answers
1
Total running time of 'm' access operation in a Splay tree .. [GATEFORUMTESTDSA]
asked
Nov 26, 2015
in
DS
by
Vinay Yadav
Active
(
2.3k
points)

228
views
datastructure
trees
+2
votes
1
answer
2
The gate book
3. The number of possible ordered trees with 3 nodes A, B, C is: A)12 B)16 C)6 D)10
asked
Aug 18, 2017
in
Programming
by
Lakshman Patel RJIT
Loyal
(
7.7k
points)

172
views
trees
0
votes
0
answers
3
Made Easy Test Series:,
A 4ary i.e., either has 0 children or has 4 children tree has 20 leaf nodes. Then the total number of nodes in the tree are ________. The correct answer given is 27 . Where my solution is wrong? Let ' I ' denote number of internal nodes so, I*4 = I + 20 1 I = 19/3 therefore 20 leaf nodes in above tree not possible.
asked
Nov 17, 2016
in
Programming
by
Shivam Chauhan
Loyal
(
8.7k
points)

187
views
madeeasytestseries
trees
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
Recent Posts
Free NPTEL Courses
IISc CSA and CDCS written test and interview Experince
IIIT Hyderabad Interview Experience
My failure, Oh wait SUCCESS journey
ALGORITHMS CHECKLIST:
All categories
General Aptitude
1.3k
Engineering Mathematics
5.2k
Digital Logic
2k
Programming & DS
3.7k
Programming
2.7k
DS
994
Algorithms
3.2k
Theory of Computation
4k
Compiler Design
1.6k
Operating System
2.8k
Databases
3k
CO & Architecture
2.6k
Computer Networks
3k
Non GATE
1k
Others
1.3k
Admissions
488
Exam Queries
436
Tier 1 Placement Questions
18
Job Queries
56
Projects
9
Follow @csegate
Gatecse
Recent Blog Comments
Hi rushit, Q4: Given a deck of 10 cards numbered ...
Arjun sir, is GO Hard copy only contain ...
yes, the book will be available. But the first ...
@Arjun Sir Can I pay money today(25 june 2018) ...
Sir I didn't get an email for GO classroom, ...
36,202
questions
43,662
answers
124,113
comments
42,944
users