edited by
8,841 views
28 votes
28 votes

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

5 Answers

Best answer
32 votes
32 votes

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.

edited by
8 votes
8 votes

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

2-3 tree

2 votes
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
Answer:

Related questions

23 votes
23 votes
4 answers
1
Kathleen asked Sep 13, 2014
4,668 views
Context-free languages are:closed under unionclosed under complementationclosed under intersectionclosed under Kleene closure
24 votes
24 votes
4 answers
4
Kathleen asked Sep 13, 2014
5,345 views
A computer system has $6$ tape devices, with n processes competing for them. Each process may need $3$ tape drives. The maximum value of n for which the system is guarant...