B-Tree Key Bounds

Problem

For a B-tree with minimum degree t (CLRS definition), every non-root node holds between t - 1 and 2t - 1 keys, non-root internal nodes have between t and 2t children, and the root holds between 1 and 2t - 1 keys. Return [min_keys_non_root, max_keys, min_children_non_root, max_children]. Assume t >= 2.

Hint

The classic split-a-full-node rule exists precisely because 2t - 1 is the maximum key count.

Test cases

case 1

in: [2]

expected: [1,3,2,4]

case 2

in: [3]

expected: [2,5,3,6]

case 3

in: [10]

expected: [9,19,10,20]

Starter codePython

def btree_key_bounds(t):
    # Your code here
    pass

3 test cases · run your code against them in the editor