Question
Download Solution PDFA complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, What is the value of n ?
Answer (Detailed Solution Below)
Detailed Solution
Download Solution PDFThe correct answer is option 3.
Key Points
If the tree is 1-ary and 'I' is an internal node, the number of leaves is 1
If the tree is 2-ary and 'I' is an internal node, the number of leaves is I+1
If the tree is 3-ary and 'I' is an internal node, the number of leaves is 2I+1
If the tree is 4-ary and 'I' is an internal node, the number of leaves is 3I+1
If the tree is 5-ary and 'I' is an internal node, the number of leaves is 4I+1
If the tree is n-ary and 'I' is an internal node, the number of leaves is (n-1)I+1
Given that leaves L= 41, internal nodes I=10
L=(n-1)I+1
41=10(n-1)+1
10n=50
n=5
∴ Hence the correct answer is 5.
Internal nodes I=10
Leaf nodes L=41
In an n-ary tree, the levels start at 0 and there are nk nodes at each level, where k is the level number.
Total number of nodes−L=I
(1+n1+n2+⋯+nK)−L=I
(1+n1+n2+⋯+nK)−41=10
(n1+n2+⋯+nK)=50
\(\frac{n(n^K−1)}{n-1}\)=50
Option verify, if n=3, nK=35 is not equal to leaves.
if n=4, nK=39 is not equal to leaves.
if n=5, nK=41 is equal to leaves. So, it is 5-ary tree.
if n=6, nK=43 is not equal to leaves.
Last updated on Jun 11, 2025
-> The UGC NET Exam Schedule 2025 for June has been released on its official website.
-> Check UPSC Prelims Result 2025, UPSC IFS Result 2025, UPSC Prelims Cutoff 2025, UPSC Prelims Result 2025 Name Wise & Rollno. Wise
-> The UGC NET Application Correction Window 2025 is available from 14th May to 15th May 2025.
-> The UGC NET 2025 online application form submission closed on 12th May 2025.
-> The June 2025 Exam will be conducted from 21st June to 30th June 2025
-> The UGC-NET exam takes place for 85 subjects, to determine the eligibility for 'Junior Research Fellowship’ and ‘Assistant Professor’ posts, as well as for PhD. admissions.
-> The exam is conducted bi-annually - in June and December cycles.
-> The exam comprises two papers - Paper I and Paper II. Paper I consists of 50 questions and Paper II consists of 100 questions.
-> The candidates who are preparing for the exam can check the UGC NET Previous Year Papers and UGC NET Test Series to boost their preparations.