GATE CSE 2003 | Question: 65

Question

Consider the following $2-3-4$ tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in constructing the tree.

What is the result of inserting $G$ in the above tree?

• A.
• B.
• C.
• D. None of the above

Comments

Option B is correct.

---

main observation in this question is that , when we have four sorted key BGHI , we can choose G or H but what to choose is initially ambiguous but when either G or H goes to root , root will become GLPU or HLPU , now again we have 2 choices choosing L or P for split , but looking at options it is clear that P(3rd element in list) is selected for split which implies that initially H(3rd element in list BGHI ) should be selected for split

---

this question is not in gate overflow pdf ( vol 3 ). may be it will be added in future

---

can anyone clear which one be the actual answer B or D?

Answer 1

b is the corect ans

when ever u instert an in ele g it is out of capacity so we push middle h into root then root also going out of capacity so me take middle ele and we form a root p

in option a first first 2 ele is pushed and in root 3rd ele is pushed

Answer 2

a) after insertion, leftmost node becomes BGHI,  node splitting takes place so G goes up, LPU becomes GLPU. further splitting moves P to top, producing the tree as given in option a.

Answer 3

Answer is c.