-
A binary tree T has 20 leaves. The number of nodes in T having two children is _____.
-
- 13
- 19
- 9
- 29
Correct Option: B
Let the number of vertices of a binary tree with ‘p’ leaves be n then the tree has–
(i) p vertices (i.e., leaves) of degree 1
(ii) one vertex (i.e.., root of T) of degree 2
(iii) 'n - p -1' (i.e., interval) vertices of degree 3
(iv) n -1edges
∴ By Handshaking theorem, p × 1 + 1 × 2 + (n – p – 1) × 3 = 2 (n – 1)
⇒ n = 2p – 1
= 39 as p = 20
⇒ n – p =19 vertices have exactly two children