GATE CSE 1992 | Question: 02,vii

Question

A $2-3$ tree is such that

1. All internal nodes have either $2$ or $3$ children
2. All paths from root to the leaves have the same length

The number of internal nodes of a $2-3$ tree having $9$ leaves could be

• A. $4$
• B. $5$
• C. $6$
• D. $7$

Comments

$\textsf{A,D}$

Answer 1

 

Why it is not possible to create with 5 & 6 internal nodes:

With 5 internal nodes,1 will be root then remains 4 nodes

With 4 nodes we need at least 2 levels 1st & 2nd level (as root is at 0th) 1st level required 2 nodes and 2nd level required 4 nodes

Hence Total=6 nodes EXACTLY (We can't have leaves at multiples levels to maintain 2nd property)

Clearly not possible.

With 6 internal nodes,1 will be root then remains 5 nodes

With 5 nodes we need at least 2 levels 1st & 2nd level (as root is at 0th) 1st level required 2 nodes and 2nd level required 4 nodes.

Hence Total=6 nodes EXACTLY(We can't have leaves at multiples levels to maintain 2nd property)

Clearly not possible