The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+15 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$
asked in DS by Veteran (52k points)
edited by | 2.3k views

4 Answers

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

answered by Boss (41k points)
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
+4 votes

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

2-3 tree

answered by Active (1.1k points)
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
answered by Boss (14.4k points)
Same here.
+1 vote

Ans should be 4 and 7

answered by Loyal (6.9k points)

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
49,540 questions
54,100 answers
71,007 users