Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Questions  >  A 3-ary tree is a tree in which every interna... Start Learning for Free
A 3-ary tree is a tree in which every internal node has exactly 3 children. The number of leaf nodes in such a tree with 6 internal nodes will be
  • a)
    10
  • b)
    23
  • c)
    17
  • d)
    13
Correct answer is option 'D'. Can you explain this answer?
Verified Answer
A 3-ary tree is a tree in which every internal node has exactly 3 chil...
It can be proved by induction that any 3-ary tree with n internal nodes will have exactly [2 (n— 1) + 3] leaf nodes.
View all questions of this test
Most Upvoted Answer
A 3-ary tree is a tree in which every internal node has exactly 3 chil...
Solution:
Given, a 3-ary tree with 6 internal nodes.
To find: Number of leaf nodes in this tree.

Approach:
In a 3-ary tree, every internal node has exactly 3 children.
So, the number of children of an internal node is 3.
Also, the number of leaf nodes in a tree is equal to the number of nodes with degree 1.

Formula:
For a tree with 'n' nodes, the sum of degrees of all nodes is (2n-2).
Using this formula, we can calculate the number of leaf nodes.

Calculation:
Given, a 3-ary tree with 6 internal nodes.
So, the total number of nodes in the tree will be = 6(internal nodes) + 1(root node) = 7.

Degree of the root node is 3, as it has 3 children.
So, the sum of degrees of all nodes in the tree will be:
3 (degree of root node) + 6 (degree of internal nodes) = 9.

Using the formula, (2n-2) = sum of degrees of all nodes in the tree.
(2n-2) = 9
2n = 11
n = 5.5

So, the total number of nodes is 5.5, which is not possible.
Therefore, there is some mistake in the given question.

Assuming that the number of internal nodes is 5 (instead of 6), we can solve the problem as follows:

Given, a 3-ary tree with 5 internal nodes.
So, the total number of nodes in the tree will be = 5(internal nodes) + 1(root node) = 6.

Degree of the root node is 3, as it has 3 children.
So, the sum of degrees of all nodes in the tree will be:
3 (degree of root node) + 5x3 (degree of internal nodes) = 18.

Using the formula, (2n-2) = sum of degrees of all nodes in the tree.
(2n-2) = 18
2n = 20
n = 10

So, the total number of nodes in the tree is 10.
And, the number of leaf nodes in the tree will be:
Number of leaf nodes = total number of nodes - number of internal nodes
Number of leaf nodes = 10 - 5 = 5.

Therefore, the correct answer is option 'D' (13), if the number of internal nodes is 6. But assuming that the number of internal nodes is 5, the correct answer is 5.
Free Test
Community Answer
A 3-ary tree is a tree in which every internal node has exactly 3 chil...
A 3-array tree is a tree in which every internal node has exactly 3 children. The number of leaf nodes in such a tree with 20 internal nodes will be _.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

A 3-ary tree is a tree in which every internal node has exactly 3 children. The number of leaf nodes in such a tree with 6 internal nodes will bea)10b)23c)17d)13Correct answer is option 'D'. Can you explain this answer?
Question Description
A 3-ary tree is a tree in which every internal node has exactly 3 children. The number of leaf nodes in such a tree with 6 internal nodes will bea)10b)23c)17d)13Correct answer is option 'D'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about A 3-ary tree is a tree in which every internal node has exactly 3 children. The number of leaf nodes in such a tree with 6 internal nodes will bea)10b)23c)17d)13Correct answer is option 'D'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for A 3-ary tree is a tree in which every internal node has exactly 3 children. The number of leaf nodes in such a tree with 6 internal nodes will bea)10b)23c)17d)13Correct answer is option 'D'. Can you explain this answer?.
Solutions for A 3-ary tree is a tree in which every internal node has exactly 3 children. The number of leaf nodes in such a tree with 6 internal nodes will bea)10b)23c)17d)13Correct answer is option 'D'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE). Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of A 3-ary tree is a tree in which every internal node has exactly 3 children. The number of leaf nodes in such a tree with 6 internal nodes will bea)10b)23c)17d)13Correct answer is option 'D'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of A 3-ary tree is a tree in which every internal node has exactly 3 children. The number of leaf nodes in such a tree with 6 internal nodes will bea)10b)23c)17d)13Correct answer is option 'D'. Can you explain this answer?, a detailed solution for A 3-ary tree is a tree in which every internal node has exactly 3 children. The number of leaf nodes in such a tree with 6 internal nodes will bea)10b)23c)17d)13Correct answer is option 'D'. Can you explain this answer? has been provided alongside types of A 3-ary tree is a tree in which every internal node has exactly 3 children. The number of leaf nodes in such a tree with 6 internal nodes will bea)10b)23c)17d)13Correct answer is option 'D'. Can you explain this answer? theory, EduRev gives you an ample number of questions to practice A 3-ary tree is a tree in which every internal node has exactly 3 children. The number of leaf nodes in such a tree with 6 internal nodes will bea)10b)23c)17d)13Correct answer is option 'D'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Explore Courses
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev