My program requires a function which takes a string of length x and compares it to a dictionary of words in a BST. The string can be a single letter character or a snippit string of an actual word. Lets say the first string x is just the letter "a", my program then needs to find all words which begin with such string. The string can be any length, it just needs to find all words that match up to the specified length. Let's say the string is "bed", "bedroom" would then be counted as one matching string. The function must run at high speeds, hence I need help with splitting the tree into just going right or left depending if root->string is less than or greater than string x. Everything is sorted with the root being the middle element of the dictionary, again, it must split the tree into a subtree and only search in that subtree since the string is either greater than or less than the root string. Your help is appreciated, thank you!

// Returns the number of strings starting with x in

// the tree with the given root.

// Must run in O(log(n) + k) time.

int completion_count_recurse(string x, Node* root);