Question 8226 – Data-Structures

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 – 1 edges
∴ 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