The Gateway to Computer Science Excellence
+18 votes
2.9k views

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.

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

6 also possible ans

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

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

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

by
+1
In the second diagram you have made 10 leaves . Plz see it .Question is asking about 9 leaves only.
+1
@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
by
0
Same here.
+1 vote

Ans should be 4 and 7

by

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
201,930 comments
95,355 users