![GATE 2015 [Set-2]](https://solutionsadda.in/wp-content/uploads/2019/05/green-new-logo.png){kind=logo}
Question 8191 – Data-Structures
April 17, 2024Question 8395 – Data-Structures
April 17, 2024GATE 2015 [Set-2]
| Question 14 |
A binary tree T has 20 leaves. The number of nodes in T having two children is _________.
| 19 | |
| 20 | |
| 21 | |
| 22 |
Question 14 Explanation:
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
(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
Correct Answer: A
Question 14 Explanation:
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
(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