It works by creating a new node for each part of the word, using existing nodes if they're already in place. You can see in this diagram an example structure after an insertion of several words.
In the above diagram the words ANT, AND, BATS have been added into the data structure. You'll notice that the word BATS can also be the word BAT and that becomes a part of the structure, setting a value at each node to state if this is a place that a word terminates.
I defined the type to have 2 options. The root node, which we want to basically ignore after we've looked through it's children and the node for storing data. It has a char for storing the value, a list of sub nodes and a bool to state whether this is where a word terminates.
The first part is to get inserting nodes into the structure sorted. There are some similarities to the BST, but my first attempt was very convoluted, and eventually was cut down into this:
There are probably some ways to simplify this further, but it does state the intention of the function clearly.
Much like with the BST, insertion was the trickier part of the important steps, and looking up a word was similar to insertion but simpler. We just want to keep going down the tree until we either run out of letters for the word we're looking up, in which case we want to check for a flag to see if this is a word termination node, or until we run out of tree, in which case it's obviously not a word.
Some testing verified that it behaved as expected, with a fairly simple program and a few breakpoints.
Hopefully in the next post, we'll use it for something a bit more interesting.