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

Programming and data structure miscellaneous

Programming & Data Structure

  1. Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are _______.
    1. 199
    2. 89
    3. 109
    4. 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



Your comments will be displayed only after manual approval.