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$):

enter image description here

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!

  • 1
    $\begingroup$ Welcome to COMPUTERSCIENCE @SE. You have a task. You present your thoughts about it (what would keeping the [number of keys] before each key mean regarding not change time complexity of insert - think about inserting a new lowest key). What is your answerable question? $\endgroup$
    – greybeard
    Commented May 26, 2020 at 6:14

1 Answer 1


First take the case when you don’t have any key repeated: you can use an ordinary Binary Search Tree (BST) and perform an inorder traversal for searching the required key. Since inorder traversal gives you the keys in sorted order, so you can simply maintain a counter which you increase every time you visit a new node.

Since, you want to allow multiple occurrences of keys, you need need to modify the node to have a integer to hold the number of times that key has been added.

It’s quite easy to fill the details.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.