GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 14

Question

A  B-Tree of order $m$ is an $m$-way search tree. What is the minimum number of keys that can be stored on the leaf level of a B-Tree of order 20 with 3 levels? (Note: the root of a tree counts as its first level)

Comments

Sir, I have a question in this answer, since we have odd number of keys per node, i.e. here there are 19 keys per node so when we add the 20th key to any node it divides the node in half (9 keys a left side, 1 key at upper level and, 10 keys at right side).
If we follow this and think of it as divide node has went on third level and the break is so in the 2nd level.
Then the 9 keys on left = 10 pointers on left node each having 9 keys  = 90 keys in left side
and 10 keys on right side = 11 pointers, with 10 pointers having 9 keys and 1 pointer with 10 keys) =100
therfore answer should be 190.

can u please help me with what is wrong in this? and let me know abt a test case with Even order giving the answer in that manner?

Answer 1

We need to find the minimum keys at the leaf level. For this, we have to consider the minimum everywhere.
At root node (Level 1): 1 node, 2 child pointers, 1 key.
At Level 2: 2 nodes, 10 child pointers per node.
At Level 3: 20 nodes, 9 keys per node.

So, the answer is 180.

Answer 2

What a silly mistake I did here

I calculated Total=1+(9*2)+(20*9)

Answer 3

my answer is coming like this

first level = 1 node

second level= 2 nodes ( 9 child , 10 child )

third level= 20 nodes ( 19 having 9 child, 1 having 10 child)

please clarify

Comments

i think third level should be 21 nodes (20 with 9 keys and 1 with 10)