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

  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$
in DS by
edited by | 2.9k views

4 Answers

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

edited by
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..

+6 votes

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

2-3 tree

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.
+2 votes
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
Same here.
+1 vote

Ans should be 4 and 7


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,513 answers
95,355 users