# Can you have a binary search tree with O(logn + M) property for the following case

Let $n$ be the number of strings which are sorted in lexicographical order and stored in a balanced binary search tree. You are provided with a prefix $x$ of which $M$ strings have the prefix $x$. I have devised the following algorithm, where I search until I find the first occurence of the prefix $x$ in one of the nodes. After that I run an inorder traversal on it, such that I print only the ones, that have prefix $x$ and are in order.

For example of sorted strings: $[ACT,BAT,CAT,CAB]$ and the prefix $x = CA$, I would print $CAT$ and $CAB$.

• From your wording (already improved by Dave) I have no idea what you are trying to do and what your quesiton is. Please edit and take more care with your language. My guess: You want to find all strings with prefix $x$ from a given set of strings. You want to do so in a given time (asymptotically). Your problem is finding a proper data structure. Or do you have/want to use BSTs? – Raphael Oct 29 '12 at 9:46
• If Raphael's interpretation is correct, you may want to look at Tries (en.wikipedia.org/wiki/Trie), which would seem to me the most efficient method. You can't get $O(\log n)$, as you may have to print out many strings (more than $O(\log n)$ of them). – Luke Mathieson Oct 29 '12 at 10:02
• I want to prove that i can make an algorithm that can go through the tree and find all the keys with the prefix "CA". in O(lgn + M) time , O(lgn) is for finding the first node of occurance of "CA" prefix key, and O(M) to go through an find the remaining successor or predecessor . I dont know how to prove, that successor and predecessor() function will run in O(M) time – user1675999 Oct 30 '12 at 3:22
• @user1675999 So you want to use the BST, and not concerned with other data structures that might be more efficient? If you are ok with other data structures, a trie might be a good starting point as Luke mentions above. – Paresh Oct 30 '12 at 16:57

The data structure you are looking for is called a range tree. Range trees are usually used for geometric data, but they can be used here as well. In 1d, a range tree is simply a balanced binary search tree with the data stored at the leaves and the internal nodes augmented with the min and max element stored in the subtree. They have running time $O(\log n+ k)$ where $n$ is the total number of objects in the tree and $k$ is the number of objects reported. You will have to structure your queries slightly differently to use a range instead if a prefix. So add a special min and max character to your alphabet, call them 0 and 1 for convenience. Now to find all strings with prefix "CA", " you would search for all strings in the range (CA0, CA1).