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.
DSA
+6
votes
395
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
Veteran
(
21.4k
points)

395
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
Veteran
(
23.4k
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
Loyal
(
3.8k
points)
edited
Nov 20, 2016
by
kirti singh
comment
@kirti plz verify ur formula.
I & L should be swapped in ur formula.
yep.. thats my mistake.. it should be L=I(n1)+1
and then acc to that, ur answer is right.. thanku for correcting me..
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.1k
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 26, 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 27, 2015
in
DS
by
Vinay Yadav
Loyal
(
3.7k
points)

216
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
Boss
(
6.7k
points)

130
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
Boss
(
9.2k
points)

175
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
isro sc 2017 2nd paper
Which college to expect?
Interview Guidance
CDAC CoursesAugust session
Counselling...
All categories
General Aptitude
1.2k
Engineering Mathematics
4.7k
Digital Logic
1.9k
Programming & DS
3.5k
Programming
2.5k
DS
947
Algorithms
3k
Theory of Computation
3.7k
Compiler Design
1.5k
Operating System
2.7k
Databases
2.8k
CO & Architecture
2.5k
Computer Networks
2.9k
Non GATE
837
Others
1.2k
Admissions
284
Exam Queries
398
Tier 1 Placement Questions
17
Job Queries
51
Projects
7
Follow @csegate
Gatecse
Recent Blog Comments
Okay Thanks
i think they call everyone ith a score higher ...
@raviyogi Do you know what was the cutoff ot IIT ...
I think the exam has not yet been created.
Then why it's not appearing as a separate exam in ...
33,712
questions
40,256
answers
114,368
comments
38,885
users