# Enhance B-Tree with find(k) function

I have a question to enhance a B-Tree and add a function called find(k) which gets a key – k and returns the index of it in the sorted keys of the tree, using $$O(N)$$ space complexity, and it needs to be in $$O(t \cdot \log_t{n})$$ time complexity. I also need to show that the function does not make the regular functions (insert, delete, split child) any different then what they used to be before ( time complexity- wise)

for example, for this tree (Only example! max degree = 3, t=2 because $$MaxDeg = 2 \cdot t – 1$$):

find(50) would return: 6 (because its in the sixth element of the sorted keys: 10 10 20 20 20 50 60 70 80)

I thought about storing how many keys are before each key, and thus we can actually do it in $$O(1)$$ but it seems unrealistic, if the question asks for $$O(t \cdot log_t{n})$$

Thank you!