Question

A binary tree T has 20 leaves. The number of nodes in T having two children is _______.

Answer 1

CASE I: Root node with two children (degree 2)

∑d_i = 2 × 1 + i₁ × 2 + i₂ × 3 + l × 1

where i1 is the number of internal nodes with one child (degree2) and i2 is the number of internal nodes with two children (degree 3)

Hence using handshating lemma:

\(\frac{{\sum {d_i}}}{2}\; = \;\# edges\; = \;1\; + \;{i_1}\; + \;{i_2}\; + \;l - 1\;\)

2 + 2i₁ + 3i₂ + l = i₁ + i₂ + l

i₂ = l – 2

∴ Total number of internal nodes with two children = l – 2

and total number of nodes with two children = l – 2 + 1 (root)

 = l – 1

CASE 2 : Root node with one child

∑d_i = 1 × 1 + 3i₂ + 2i₁ + l

\(\frac{{\sum {d_i}}}{2}\; = \;1\; + \;{i_1}\; + \;{i_2}\; + \;l\)

1 + 3i₂ + 2i₁ + l = 2 + 2i₁ + 2i₂ + 2l

i₂ = l – 1

∴ Total number of nodes with two children = l – 1

Calculation:

l = 20

∴ i₂ = I - 1 = 20 - 1 = 19