B+ Tree Leaf Order Keys

Problem

Simulate the leaf level of a B+ tree with insert and range queries.

operations contains "insert" (values[i] is the key, kept in sorted order with duplicates allowed), "keys" (records the whole leaf), or "range" (values[i] is [lo, hi], records the keys in that inclusive range).

Return the list of recorded results.

Hint

B+ tree leaves are a sorted list of keys, so range scans are contiguous.

Test cases

case 1

in: [["insert","insert","insert","keys"],[3,1,2,0]]

expected: [null,null,null,[1,2,3]]

case 2

in: [["insert","insert","range","range"],[5,8,[4,6],[8,9]]]

expected: [null,null,[5],[8]]

case 3

in: [["range"],[[1,3]]]

expected: [[]]

case 4

in: [["insert","insert","insert","range"],[2,2,3,[2,2]]]

expected: [null,null,null,[2,2]]

Starter codePython

def bplus_leaf_ops(operations, values):
    # Your code here
    pass

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