Question 1588 – Nielit Scientist-B IT 22-07-2017
December 12, 2023Question 1777 – Nielit Scientific Assistance IT 15-10-2017
December 12, 2023Question 1770 – Nielit Scientific Assistance IT 15-10-2017
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is
Correct Answer: C
Question 2 Explanation:
● The number of nodes n in a full binary tree, is at least n = 2 h + 1 and at most n = 2 h+1 − 1 , where h is the height of the tree. A tree consisting of only a root node has a height of 0.
● The number of leaf nodes l in a perfect binary tree, is l = ( n + 1 )/2 because the number of non-leaf (a.k.a. internal) nodes
● This means that a perfect binary tree with l leaves has n = 2 l − 1 nodes.
● In a balanced full binary tree, h = ⎡ log 2 (l)⎤ + 1 = ⎡ log 2 ((n + 1 )/2)⎤ + 1 = ⎡ log 2 (n + 1 )⎤
● In a perfect full binary tree, l = 2 h thus n = 2 h+1 − 1
● The maximum possible number of null links (i.e., absent children of the nodes) in a complete binary tree of n nodes is ( n + 1 ) , where only 1 node exists in bottom-most level to the far left.
●The number of internal nodes in a complete binary tree of n nodes is ⎣ n/2⎦ .
● The number of leaf nodes l in a perfect binary tree, is l = ( n + 1 )/2 because the number of non-leaf (a.k.a. internal) nodes
● This means that a perfect binary tree with l leaves has n = 2 l − 1 nodes.
● In a balanced full binary tree, h = ⎡ log 2 (l)⎤ + 1 = ⎡ log 2 ((n + 1 )/2)⎤ + 1 = ⎡ log 2 (n + 1 )⎤
● In a perfect full binary tree, l = 2 h thus n = 2 h+1 − 1
● The maximum possible number of null links (i.e., absent children of the nodes) in a complete binary tree of n nodes is ( n + 1 ) , where only 1 node exists in bottom-most level to the far left.
●The number of internal nodes in a complete binary tree of n nodes is ⎣ n/2⎦ .
2 h
2 h-1 -1
2 h+1 -1
2 h+1