28 votes 28 votes A $2-3$ tree is such that All internal nodes have either $2$ or $3$ children 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 $4$ $5$ $6$ $7$ DS gate1992 tree data-structures normal multiple-selects + – Kathleen asked Sep 12, 2014 • edited Apr 19, 2021 by Lakshman Bhaiya Kathleen 9.0k views answer comment Share Follow See 1 comment See all 1 1 comment reply Akash 15 commented Feb 7 reply Follow Share $\textsf{A,D}$ 0 votes 0 votes Please log in or register to add a comment.
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. Akash Kanase answered Nov 20, 2015 • edited May 5, 2021 by soujanyareddy13 Akash Kanase comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Sayan Bose commented Aug 12, 2018 reply Follow Share What do you mean by leaf has child? 1 votes 1 votes vishalshrm539 commented Sep 6, 2018 reply Follow Share I think he meant non-leaf 0 votes 0 votes chirudeepnamini commented Oct 2, 2019 reply Follow Share Correct me if iam wrong : there are 5 possible structures with the given property.. 10 votes 10 votes Please log in or register to add a comment.
9 votes 9 votes In 2-3 Tree for 9 leaves, internal nodes can be 4 or 7 mint answered Jan 26, 2017 mint comment Share Follow See all 2 Comments See all 2 2 Comments reply dragonball commented Apr 25, 2017 reply Follow Share In the second diagram you have made 10 leaves . Plz see it .Question is asking about 9 leaves only. 1 votes 1 votes mint commented Apr 26, 2017 reply Follow Share @ashwina, yes you are correct, that was a mistake. please assume 9 leaf nodes in the 2nd tree. 1 votes 1 votes Please log in or register to add a comment.
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 Bhagirathi answered Sep 18, 2014 Bhagirathi comment Share Follow See 1 comment See all 1 1 comment reply Rajarshi Sarkar commented Apr 25, 2015 reply Follow Share Same here. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Ans should be 4 and 7 rishu_darkshadow answered Oct 6, 2017 rishu_darkshadow comment Share Follow See all 0 reply Please log in or register to add a comment.