-
Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are _______.
-
- 199
- 89
- 109
- None of the above
Correct Option: A
Let the number of leaf nodes of a binary tree with ‘n’ vertices be ‘p’ then the tree has
(i) ‘p’ vertices of degree ‘1’
(ii) one vertex (i.e. root of T) of degree ‘2’.
(iii) 'n – p – 1' vertices of degree ‘3’
(iv) 'n –1' edges
∴ By Handshaking theorem, p × 1 + 1 × 2 + (n – p –1)×3 = 2(n –1)
⇒ n = 2 p – 1
= 399 as p = 200
∴ Number of nodes having exactly two children are n – p i.e., 199