Sketch out an algorithm.  You don't have to write code.  But given a trie and given a string, design an algorithm that will print all strings in the trie that begin with the given string, in alphabetical order.  For example, if the string were CAT, you should print CAT, CATAN, and CATHETER, if these strings are in the trie.  Try to design an algorithm that does this recursively.

If there is no node corresponding to the first letter of the string, then there are no valid strings to print.

If the input string is empty:  The empty string is the prefix of every single string.  So if the input string is "", then all strings in the trie work.  (The original input string followed by all possible strings in the trie from this point down.)

If there IS a node corresponding to the first letter of the string, go to that node, remove the first letter of the string, and recurse at this point.  So, if my input string is CAT, and I can get to a C.  I go to the C, and then from this point, start the algorithm again, but now I'm searching for AT.


Design an algorithm that will print all strings in the trie that contain the given string, in alphabetical order.  So if I'm given CAT, I not only have to find CAT, CATAN, and CATHETER, but also HECATE, LOLCAT, CONCATENATE.

Base cases:  empty string as given string:  everything is valid.

Empty trie:  nothing will work (unless we're searching for the empty string).

Recursive case:

 There are two things to consider.  The string begins "CAT" (say) or it contains it somewhere.  So, we have to recursively consider all strings BEGINNING with "AT" starting from the "C" node.  We also have to consider every node below my current node CONTAINING "CAT".

For example, if I have a "B" node I can get to, I can go there and look for "CAT" from there.  If I have an "F" node, I go there and look for "CAT".  If I have a "C" node, I still need to check that one, too, because this string might not begin with "CAT" but still has a "CAT" in there.  (Like "CONCATENATE.").  (From the "C" node, you will have to do two searches, for strings BEGINNING with "AT" and for strings containing "CAT".)

We have to look for strings that BEGIN with with the input string  AND we have to look for strings that CONTAIN the input string.