A binary tree T has n leaf nodes. The number of nodes of degree 2 in T...
Because for 2 degree node, every time ‘2’ leafs are added and number of nodes increases is '1'. So number of nodes with degree 2 is always one less than number f leafs present in tree.
View all questions of this test
A binary tree T has n leaf nodes. The number of nodes of degree 2 in T...
Explanation:
A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. The number of nodes of degree 2 in a binary tree can be determined by counting the number of nodes with two children.
Let's analyze the given options:
a) log2n: This option suggests that the number of nodes of degree 2 is logarithmic with respect to the number of leaf nodes. However, this is not necessarily true. The number of nodes of degree 2 can vary depending on the structure of the tree, and it is not directly related to the number of leaf nodes.
b) n - 1: The number of nodes of degree 2 in a binary tree is always one less than the total number of nodes in the tree. This is because, in a binary tree, each node has at most two children. Therefore, if a binary tree has n nodes in total, the maximum number of nodes of degree 2 is n - 1.
c) n: This option suggests that the number of nodes of degree 2 is equal to the total number of nodes in the tree. This is incorrect because not all nodes in a binary tree have two children. Only some nodes, specifically the internal nodes, have two children.
d) 2n: This option suggests that the number of nodes of degree 2 is twice the total number of nodes in the tree. This is incorrect because each node in a binary tree can have at most two children. Therefore, it is not possible for the number of nodes of degree 2 to be greater than the total number of nodes.
Conclusion:
The correct answer is option b) n - 1. The number of nodes of degree 2 in a binary tree is always one less than the total number of nodes in the tree.