The Gateway to Computer Science Excellence

+18 votes

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

A $2-3$ tree is such that

- All internal nodes have either $2$ or $3$ children
- 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

- $4$
- $5$
- $6$
- $7$

+22 votes

Best answer

Answer (**a**) 4, (**d**) 7

$4 \rightarrow$ When each leaf has $3$ childs. So $9/3 = 3$ Internal nodes, Then one internal node those internal nodes.

$7 \rightarrow$ When each leaf has $2$ childs & one leaf out of $4$ get $3$ childs. Ex $\rightarrow 8/4 = 2$ child per internal node. Then one of that internal node get extra third child. Then $2$ internal nodes to connect these $4$. Then $1$ internal node to connect this $2$. So $4+2+1 = 7$.

No other way is possible.

+5

@srestha plz check bcoz it not satisfy this which is given in question **All paths from root to the leaves have the same length.**

+6 votes

52,345 questions

60,513 answers

201,930 comments

95,355 users