**Max** is asked, so we have to use left biasing which will give 4 leaf node splits. Thus **ans**** C)**

The Gateway to Computer Science Excellence

+40 votes

The following key values are inserted into a $B+$ - tree in which order of the internal nodes is $3$, and that of the leaf nodes is $2$, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it. The $B+$ - tree is initially empty

$10$, $3$, $6$, $8$, $4$, $2$, $1$

The maximum number of times leaf nodes would get split up as a result of these insertions is

- $2$
- $3$
- $4$
- $5$

+53 votes

Best answer

In this question they have asked only to count leaf node splits.

So, after discussing with my friends on Facebook, I found that you will get two different answers depending on which convention you follow.

Convention 1: put the middle element in the left node, if you follow this you will get $4$ as answer.

Convention 2: put the middle element in the right node, if you follow this you will get $3$ as answer.

$4$ splits:

- after inserting $6$
- after inserting $4$
- after inserting $2$ (there will be an internal node split and a leaf node split)
- after inserting $1$

Correct Answer: $C$

+8

Yes, true but they have clearly asked **MAXIMUM** number of splits which would be achieved only using left biasing B+ tree. So, 4 is the only correct answer.

0

which order you are following , is it 3 or 2 .

Please explain me this line "order of the internal nodes is 3, and that of the leaf nodes is 2"

Please explain me this line "order of the internal nodes is 3, and that of the leaf nodes is 2"

+6

"The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it."

Read this statement from the question carefully. Both have same meaning.

Read this statement from the question carefully. Both have same meaning.

+28

Those you want to visualize the tree. Draw the tree here by simply inserting the value. It will be right biased.

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

0

You're doing it completely wrong. Its clearly stated in question that order of internal node is maximum number of tree pointers in each node and they have given this order 3.

If there are 3 tree pointers then there must be 2 keys in each internal node. You have takes 3 keys in each internal node.

If there are 3 tree pointers then there must be 2 keys in each internal node. You have takes 3 keys in each internal node.

+10

Let me know if below is correct sequence of steps for insertion into a B+ tree (left-biased).

and Final B+ tree

Assume that from left to right leaf nodes are connected (as they are), via block pointers.

+1

5 is the answer.

There’s an awesome B+ tree visualizer here : http://goneill.co.nz/btree-demo.php

Someone dedicated his/her time creating this great tool, and total splits are 5 according to this.

0

Best way to visualize the steps: https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

I think only due to this ambiguity, whether to choose left biasing or right biasing they stopped asking such question after 2009.

I'm getting answer 3 according to above website steps.

+2

@himanshu6398-Yes total 5 splits are there but 1 is of non-leaf node and question asks for the split of leaf nodes only.

0

@Ayush It seems that your leaf node containing 6 is in wrong position. It should be in the subtree immediately after 6 in the parent node

0

When u inserting 2, u have splitted leaf node as well as internal node

right?

But why u splitted internal node at that time?

Internal node order is 3, not 2

So, it should be inserted after insertion of 1

right??

0

@srestha maam when we split node what goes in upper internal node max of left subtree or min of right subtree?

In the above question if I take least element of right subtree in the upper node then I am getting 5 as a answer.

+17 votes

THANK YOU

Correct me if I am wrong !!

+9 votes

i have tried to draw it and getting** "4"** split of leaf node using **"left biasing"**

**correct me if you found any mistakes**

0

@prateek.. Yes u r correct but can u pl tell me what ans are u getting if we follow right biasing.. Bcz m getting 3..with right biasing also.. Am i correct?

+2

Here, order is 3 so we can take only 2 key values in the internal nodes ,

so there should be split in the node having value 3, 4, 6 as in que --

The maximum number of times leaf nodes would get split up as a result of these insertions is asked

so ans would be 4 only .

so there should be split in the node having value 3, 4, 6 as in que --

The maximum number of times leaf nodes would get split up as a result of these insertions is asked

so ans would be 4 only .

+1

order of the internal nodes is 3 and order of internal nodes is the maximum number of tree pointers in each node

But at step 6, Your internal node has 4 poimters .

0

@prateek in ur ans at insert1 there are 2 split 123(at level 3)and 2346 (at level 2)

then why r u counting it as 1split .. if we consider 2split at insert1 then there are 5split...any one plz explain

then why r u counting it as 1split .. if we consider 2split at insert1 then there are 5split...any one plz explain

0

@prateek

https://gateoverflow.in/453/gate2008-41

in the que given in above link ,last step is similar to the last step of this que ... but in that. Que split at leaf node and split at non leaf node is considered as 2split and then is this que how r u counted split at leaf node and non lead node as single split....

https://gateoverflow.in/453/gate2008-41

in the que given in above link ,last step is similar to the last step of this que ... but in that. Que split at leaf node and split at non leaf node is considered as 2split and then is this que how r u counted split at leaf node and non lead node as single split....

+5 votes

answer is **3** if followed right biasing, means, putting middle element in right node.

and, answer is **4 **if followed left biasing, means, putting middle element in left node.

but actually, which to follow officially ?

however, maximum is asked in this question, so ,there is a reason to choose left biasing here.

+5 votes

*The** maximum number of times leaf nodes would get split up as a result of these insertions is* so the correct ans should be **4 **only

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,292 answers

198,230 comments

104,909 users