# PSET5 speller - I cannot understand tries at all

I am so completely lost. I completed PSET5 with a hash table, and the concept of hash tables makes sense to me. Now I am attempting to do it with a trie, and I am just so confused I don't even know where to start. I have watched the videos several times and searched for resources online, but I suppose I'm not asking the right questions, because I can't find much information on them.

I don't even understand the objective of a trie. With a hash table, it makes intuitive sense - take a word, store it in a node, chain those nodes together into a linked list, put them in a hash table, then you can access each node by hashing a word and traversing the linked list. With a trie, what is being stored? How can one "load" a dictionary? How is the boolean is_word related at all to retrieving the word?

I suppose this is a stupid question. I would really like to understand this but I'm so completely confused I don't even know where to start. I have absolutely no clue. Could someone shed some light onto this, or point me to some resources that might help? Thanks.

Don't feel bad, it took me a little while to wrap my head around the concept originally. ;-)

A trie is essentially a tree representation of a bunch of words. The root of a tree and every node can potentially point at up to 26 nodes, but let's keep it simple. Say that you have to build a trie with 3 words, "am", "at", and "ad". When the trie is finished, the root will have a root->next pointer that contains the address of the "a" node. Moving down the trie, the "a" node would have next pointers to the "d", "m", and "t" nodes. Since each of these nodes is the end of a word, they would also have the is_word flag set to true. Note that these nodes could also point at other words. For example, if a trie had the words cat and cater, the t node would show is_word = true and would have a pointer to the "e" node on the next level.

That's a brief description of how a trie looks. Here's the part that is probably confusing you. It's natural to think that the actual letter or the word should be stored somewhere. It's obvious, isn't it?

Well, no. In a trie, you don't store the letter or the word (unless you really want to). The key fact is that the EXISTENCE of a node represents the letter. Take the trie above. Now, imagine checking for the existence of the word "ax". The process is simple. Go to the root and check the next pointer to "a". It has an address stored, so the letter a as the first letter exists. You then go to that "a" node, which was probably the address stored in `root->next[0]`, and check the pointer to the "x" node. This time, the node is set to NULL, meaning that the node for that letter doesn't exist. THAT means that there is no word starting with "ax". By the way, the full path to the x would be `root->next[0]->next[23]` or, if you're using a cursor, the last pointer would be `cursor->next[23]`.

So, the secret is that the existence of a series of nodes represents the existence of a word. Extending the descriptiion, "cat" would be represented by the node string of `root->next[2]->next[0]->next[19]` and `root->next[2]->next[0]->next[19]->is_word = true`. The actual words or letters themselves aren't stored anywhere.