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

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
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
519
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
(
17.7k
points)

519
views
answer
comment
0
@Habibkhan
0
Same question:
https://gateoverflow.in/66314/dsa
Your identity must be verified before you can post a comment. Please wait if already uploaded identity proof or upload your proof
here
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
(
23.4k
points)
selected
Sep 4, 2016
by
ManojK
comment
Your identity must be verified before you can post a comment. Please wait if already uploaded identity proof or upload your proof
here
+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.6k
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.
Your identity must be verified before you can post a comment. Please wait if already uploaded identity proof or upload your proof
here
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
Your identity must be verified before you can post a comment. Please wait if already uploaded identity proof or upload your proof
here
0
votes
ANswer can be 33,37,41.See the image attached
answered
Nov 25, 2017
by
Anubhav Kaushik
(
23
points)
comment
Your identity must be verified before you can post a comment. Please wait if already uploaded identity proof or upload your proof
here
← 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, 2018
in
Graph Theory
by
Sandy Sharma
Active
(
1.2k
points)

55
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, 2018
in
Graph Theory
by
Sandy Sharma
Active
(
1.2k
points)

101
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, 2018
in
Graph Theory
by
Sandy Sharma
Active
(
1.2k
points)

182
views
discretemathematics
trees
0
votes
0
answers
4
DSATest 3Question 5
Consider following statements about tripartite graph, i.e. TPG, which contains three subsets of vertices of graph as A,B and C: (i) Minimum number of edges in a cycle in a TPG which passes through all three subsets of vertices is 6. (ii) A complete TPG can be colored with atmost 3 ... are true: (A) (i) only (B) (iii) only (C) (ii) and (iii) only (D) (i) and (ii) only
asked
Sep 18, 2018
in
Graph Theory
by
Sandy Sharma
Active
(
1.2k
points)

41
views
trees
discretemathematics
0
votes
1
answer
5
DSATest 3Question 3
A quinpartite graph is a graph whose vertices can be partitioned into five groups such that no two vertices in same group are connected via some edge. The maximum number of edges in a quinpartite graph with 10 vertices, where cardinalities of those five sets are given as {2,3,2,1,2}, is: (A) 16 (B) 20 (C) 26 (D) 39
asked
Sep 18, 2018
in
Graph Theory
by
Sandy Sharma
Active
(
1.2k
points)

83
views
trees
+3
votes
0
answers
6
Total running time of 'm' access operation in a Splay tree .. [GATEFORUMTESTDSA]
asked
Nov 26, 2015
in
DS
by
Vinay Yadav
Active
(
2.4k
points)

252
views
datastructure
trees
0
votes
0
answers
7
Data structures
asked
Sep 28, 2018
in
Programming
by
Vaishnavi01
(
143
points)

76
views
datastructure
trees
empty
binary
binarytree
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
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
The day that made me an IIScian :)
Unanswered Previous year GATE/TIFR questions
From being a Failure to getting into IISc  (Rank 888, Score 692)
My interview experience at IITs/IISc
IIT Delhi CSE Mtech interview 14 may
All categories
General Aptitude
1.8k
Engineering Mathematics
7.3k
Digital Logic
2.9k
Programming & DS
4.9k
Programming
3.6k
DS
1.3k
Algorithms
4.3k
Theory of Computation
6k
Compiler Design
2.1k
Operating System
4.2k
Databases
4.1k
CO & Architecture
3.4k
Computer Networks
4.1k
Non GATE
1.4k
Others
1.4k
Admissions
596
Exam Queries
577
Tier 1 Placement Questions
23
Job Queries
72
Projects
18
Follow @csegate
Recent Blog Comments
a heartiest congratulations mam :)
Congratulations
Thank you
Very Nice. Congratulations ))👍
49,541
questions
54,083
answers
187,208
comments
70,992
users