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
Exam Category
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
270
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
(
20.5k
points)

270
views
Facebook
Google+
Twitter
answer
comment
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
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:>>
(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
(
21k
points)
selected
Sep 4, 2016
by
ManojK
comment
Please
log in
or
register
to add a comment.
+1
vote
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.6k
points)
edited
Nov 19, 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
Junior
(
893
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
Loyal
(
3.3k
points)

168
views
datastructure
trees
0
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
in
Programming
by
Lakshman Patel RJIT
Active
(
1.3k
points)

80
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
(
8.1k
points)

131
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
How to be productive?For all Members,GATE Aspirants, everybody associated with "GO Family"
How to Do preparation for Gate2018
How to write nice answers/questions in GO
Organizing NET Questions
Easy or Right: The Choice is Yours
All categories
General Aptitude
1.1k
Engineering Mathematics
4k
Digital Logic
1.7k
Programming & DS
2.9k
Programming
2.1k
DS
831
Algorithms
2.6k
Theory of Computation
3.1k
Compiler Design
1.2k
Operating System
2.3k
Databases
2.3k
CO & Architecture
2.1k
Computer Networks
2.4k
Non GATE
795
Others
1.2k
Admissions
244
Exam Queries
417
Tier 1 Placement Questions
16
Job Queries
40
Projects
4
Follow @csegate
Gatecse
Recent Blog Comments
Hi @
thanks a lot sir
I hope everybody derives the best out of this. :)
For creating automatas you can also ...
Really one of the Great post.Thanks papesh.
28,834
questions
36,689
answers
90,626
comments
34,641
users