# cant wrap my head around implementing this trie

So in theory the concept of a trie makes a lot of sense, but I'm really missing something when it comes to putting it down into code. Any help would be soooo greatly appreciated. I've scoured the internet for help but still missing a few connections. Ok... Here's what i'm getting... or think i am. Sorry this is gonna be long...

First off children[0] doesnt hold any actual value at that index right? its literally just a pointer. So 'a' doesnt actually exist anywhere other than that its essentially children[a]?

You create and malloc a root node, the is_word bool is false and the children pointer isnt pointing anywhere.

Then you create a new node that equals the root...

Then you iterate over the word to input the characters one at a time...

If the character is a letter or ' then you create/malloc a new node and the is_word is still set to false.

When you reach the last letter of the word you change is_word to true... that is essentially adding \0 right? (Also, instead of checking for NULL would saying if i == length of the word work?)

That potentially takes care of one word in the trie... I cant figure out how then to start another one. is it literally the same thing? and the way you find different words is just by seeing if the index of children is null? if so there's no letter if not then keep checking for null until you find is_word = true?

Typing this out helped a bit but still confusing.. Thanks for the help!

First off children[0] doesnt hold any actual value at that index right? its literally just a pointer. So 'a' doesnt actually exist anywhere other than that its essentially children[a]?

you probably get that correctly, but just to put it in a more suitable form:

• yes `children[i]`, where `i` is a valid index, is a pointer. a pointer may hold a value (a memory address).
• no, `'a'` doesn't have to physically exist.
• `children['a' - 'a']`, aka `children[0]`, (not `children[a]`) is a pointer to a trie node that may represent an `'a'` (or an `'A'`).

You create and malloc a root node, the is_word bool is false and the children pointer isnt pointing anywhere.

ideally, the root itself should be an array of pointers to trie nodes. each trie node being pointed to by one of these pointers should represent an alphabetical character as the first character in a word.

for example, the trie node pointed to by `root['a' - 'a']` should represent an `'a'` (or an `'A'`) as the first character of some word, the trie node pointed to by `root['b' - 'a']` should represent a `'b'` (or a `'B'`) as the first character of some word, and so on.

each trie node should have an array of children (also pointers to trie nodes) and a boolean flag that should be set to `true`, if the character that this trie node represents is an end of a word.

as I just mentioned, the array of children should be an array of pointers to trie nodes as well. each trie node being pointed to by a pointer in that array represents an alphabetical char or an apostrophe as the character following the parent in a word.

this may be a little confusing, so here is an example:

``````root['h' - 'a'] // points to trie node that represents 'h' as first char in a word
root['h' - 'a']->children['i' - 'a'] // points to trie node that represents 'i'
// as second char, after 'h', in a word
``````

if you have memory allocated for `root['h' - 'a']` and `root['h' - 'a']->children['i' - 'a']` (i.e., both are not NULL pointers, assuming you initialize them with `NULL` once they're defined), and `root['h' - 'a']->children['i' - 'a']->isWord` is `true`, that means that you have the word `"hi"` in your trie.

### How to insert a word in a trie?

to insert a word in a trie, you do the following:

``````calculate index of first char in word to be inserted
define a temporary pointer to trie node to act as cursor
set cursor to point to node that represents the 1st char // as in cursor = root[index]

do
ensure cursor has memory allocated for it

if current char is last char
mark node pointed to by cursor as an end of word
break
else
calculate index of next char

update cursor to point to node that represents next char
// as in cursor = cursor->children[index]
while true
``````

hope that clears any confusion! for more, watch the short on tries: https://youtu.be/TRg9DQFu0kU!

• Thanks! that was helpful. yea took awhile but finally got it. Commented May 27, 2016 at 18:15