4,720 views

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

1. $4$
2. $5$
3. $6$
4. $7$

### Subscribe to GO Classes for GATE CSE 2022

Correct Options: A;D

$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.

We are also considering root as an internal node right?
is there any specific procedure for this ques....?????????

6 also possible ans

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

yes thanks
What do you mean by leaf has child?
I think he meant non-leaf

Correct me if iam wrong : there are 5 possible structures with the given property..

In 2-3 Tree for 9 leaves, internal nodes can be 4 or 7

by

In the second diagram you have made 10 leaves . Plz see it .Question is asking about 9 leaves only.
@ashwina, yes you are correct, that was a mistake. please assume 9 leaf nodes in the 2nd tree.
Am getting only 4 and 7 4-> complete 3 ary-tree 7-> almost complete binary tree ...almost in the sense one of penultimate level node has 3 children

### 1 comment

Same here.

Ans should be 4 and 7