To avoid any confusion the order of B tree is the maximum number of children it can have.

Suppose we create a B tree of order 4 by inserting 6 distinct keys (1, 2, 3, 4, 5, 6) in any permutation, how many different structure of B trees can we get?

While inserting a new node in a B tree, going by the insertion rules from Wikipedia

A single median is chosen from among the leaf's elements and the new element.

As we can have a maximum 3 keys in a node, plus the new element totalling four keys so we can choose either the 2nd or the 3rd as the median. So the new structure will be dependent on choice of the median along with insertion order.

How do I solve this problem systematically? I've been trying to brute force it and I have found these four structures

    3           4           2,4           3,5
  /  \        /   \        / | \        /   |  \
1,2  4,5,6  1,2,3  5,6    1  3  5,6   1,2   4   6

Are there more?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.