TRIE   "try"

TRIE comes from the word reTRIEval, but no one pronounces it TREE because there's already a computer term called TREE.

It is a way of storing a set of strings for easy lookup.

SEARCHING A TRIE:

Starting with the first character of your string, follow the pointers to the following letters, working your way down the trie.  If you are able to follow pointers through the entire and you end up in a node with the end_of_string set, then you know that you have found the word.

If you following the string and you find a null pointer that you can't follow before you finish the string ("falling off the trie") you fail.

Or, you are able to follow the whole string, but when you get to the end, the end_of_string marker is not present.

ADD TO A TRIE

Follow your string through the trie until you fall off, then add the remaining letters one at a time following that point.

If you never fall off, but there's no end_of_string marker, then you add that and you're done.  If there already was an end_of_string marker, then the string was already in there, so it can't be added.

REMOVE FROM A TRIE

Easiest Case:  If the string is a prefix of another string in the trie, just set the end_of_string marker to false.

If you search for the string, and it's not even in there, then the remove fails.

Let's say it's in there, and the node corresponding to the last character has no children...you delete the nodes one at a time working your back up until you get to a node with other children or with an end_of_string marker.  (But don't delete the root no matter what.)