B+ Tree Leaf Level Count

Problem

For a B+ tree storing num_keys entries, leaves hold at most leaf_capacity keys and each internal node has at most fanout children. Fill leaves left to right, then group nodes level by level the same way. Return [leaf_count, internal_levels, total_nodes], where internal_levels counts the levels above the leaves and total_nodes includes every node. Return [0, 0, 0] when num_keys or leaf_capacity is 0.

Hint

Each level above the leaves groups the previous level into fanout-sized parents with ceiling division.

Test cases

case 1

in: [100,10,5]

expected: [10,2,13]

case 2

in: [5,10,4]

expected: [1,0,1]

case 3

in: [1,1,2]

expected: [1,0,1]

case 4

in: [1000,50,20]

expected: [20,1,21]

case 5

in: [0,10,4]

expected: [0,0,0]

Starter codePython

def bplus_level_count(num_keys, leaf_capacity, fanout):
    # Your code here
    pass

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