If T is a binary tree with number of levels as L (counting the root as level…
2017
If T is a binary tree with number of levels as L (counting the root as level 1), then the number of leaf nodes in the binary tree is at most:
- A.
2ᴸ⁺¹
- B.
2L
- C.
2ᴸ
- D.
2ᴸ⁻¹
Attempted by 439 students.
Show answer & explanation
Correct answer: D
In a binary tree, the maximum number of nodes at any level i
(starting from i = 1 for the root) is 2i-1. To achieve the maximum
number of leaf nodes, the tree must be a perfect binary tree where all leaves
reside at the last level L. Substituting i = L, the maximum number of leaf
nodes is 2L-1. Thus, Option D is correct.