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
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.
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 _.
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).