# 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

## 1 Answer

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).

As noted in the comments above, a trie is the structure one would normally use for this type or query. But the computational model used is slightly different, so it's hard to compare. The running time would be the length of your longest output string + k.

• The range tree also assumes that you can compare objects (in this case strings). In constant time, which is an assumption the trie doesn't make. The trie assumes your alphabet is constant size. – Joe Oct 30 '12 at 7:35