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
449
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.6k
points)

449
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.8k
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
0
votes
0
answers
1
DSATest 3Question 12
Let T = (V, E) be a tree and let d(v) be the degree of a vertex. Consider following statements: (i) P v∈V (2 − d(v)) = 2 (ii) If T has a vertex of degree m ≥ 2, then it has at least m vertices of degree 1. (iii) P v∈V (k − d(v)) = k, for k ≥ 2  k ∈ ... of the above statements is/are ture: (A) (i) only (B) (i), (ii) only (C) (ii) and (iii) only (D) (i), (ii) and (iii) only
asked
Sep 18
in
Graph Theory
by
Sandy Sharma
Junior
(
903
points)

10
views
trees
discretemathematics
0
votes
1
answer
2
DSATest 3Question 10
For which of the following scenarios does there exist a simple graph G = (V, E) satisfying the specified conditions? (A) It has 3 components 20 vertices and 16 edges. (B) It has 10 vertices, 38 edges, and more than one component. (C) It has 7 vertices, 10 edges, and more than two components. (D) It is connected and has 10 edges 5 vertices and fewer than 6 cycles.
asked
Sep 18
in
Graph Theory
by
Sandy Sharma
Junior
(
903
points)

15
views
trees
discretemathematics
0
votes
1
answer
3
DSATest 3Question 9
Consider following statements: (i) Every simple graph has at least two vertices of the same degree. (ii) If u is a vertex of odd degree in a graph, then there exists a path from u to another vertex v of the graph where v also has odd degree. (iii) If there are exactly ... above statements are not true? (A) (i) and (ii) only (B) (iii) only (C) (ii) only (D) None of the above
asked
Sep 18
in
Graph Theory
by
Sandy Sharma
Junior
(
903
points)

11
views
discretemathematics
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
Read/Unread questions
kvs pgt
Algorithms GO Classroom
Programming and DS GO Classroom
Discrete Mathematics GO Classroom
All categories
General Aptitude
1.4k
Engineering Mathematics
5.7k
Digital Logic
2.2k
Programming & DS
4.1k
Programming
3k
DS
1.1k
Algorithms
3.6k
Theory of Computation
4.5k
Compiler Design
1.7k
Operating System
3.2k
Databases
3.2k
CO & Architecture
2.8k
Computer Networks
3.2k
Non GATE
1.1k
Others
1.5k
Admissions
503
Exam Queries
474
Tier 1 Placement Questions
22
Job Queries
61
Projects
13
Follow @csegate
Gatecse
Recent Blog Comments
following link is Kvs_Pgt_Question Paper...
@Arjun sir how to remove such post? should i hide...
[email protected]
.Plz do share @Sanjay sharma
Please post it as question
This is blog area post it as question
39,815
questions
46,794
answers
140,934
comments
58,863
users