TRIES

How do you find the FIRST string in alphabetical order?

Go all the to the left until you find an end-of-string marker.

How do you find the LAST string in alphabetical order?

Go all the way to the right until you fall off the trie.

If you have a string in the TRIE, how can you one the one immediately after it or before it in alphabetical order?

AFTER IT:  If you have children, go all the way to the left until you hit an end-of-string marker.

APP comes before APPLE alphabetically.  Shorter strings always come before larger strings that contain the shorter string as a prefix.

So, if our end-of-string node has children, ALL of these come after ours, so to find the first one of these, we go all the way to the left until we hit end-of-string.

If you don't have children, move up until you a hit a node with a sibling greater than itself.  Follow that sibling all the way left until end-of-string is hit.

If you make it all the way to the root without ever finding a greater sibling, then there is no string after you.

How you find the first string in alphabetical that comes BEFORE you?

If you have a sibling that comes before you, follow that sibling all the way to the right until you fall off the trie.

If you don't have a sibling that comes before you, if your parent has an end-of-string marker.  Then your previous string ends at your parent.

If your parent has neither a left sibling nor an end-of-string marker, go up to your parent and start the process again.

If you make it all the way to the root and you never hit a node with a left sibling or an end-of-string marker, then you don't have a previous.

A
P
P <>
L <>
E<>  I
     C
     A
     T
     I
     O
     N


SEARCH  With a Wildcard character.

Assume ? can stand for any letter of the alphabet.

C?T   could be CAT  or COT  OR CXT

How can we easily do a wildcard search with a trie?

When you hit a ?  Try all of the children at this point.  Use a combination of iteration and recursion.

Searching a TRIE is naturally recursive anyway.  If I'm looking for CAT, all I have to is move to the C and look for AT at that point.

So, if searching C?T   move to C and then iterative try AT, BT, CT, etc.