Home » Programming & Data Structure » Programming and data structure miscellaneous » Question

Programming and data structure miscellaneous

Programming & Data Structure

  1. A binary tree T has 20 leaves. The number of nodes in T having two children is _____.
    1. 13
    2. 19
    3. 9
    4. 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



Your comments will be displayed only after manual approval.