Pset5: Misunderstanding tries and method to assign letter to an array inside a struct

Question

Before posting, I've searched a lot here and there on the Internet to find the answers to my questions myself and I did code something that eventually works.

My issue is that I've re-rewrote some parts of my code based on working bits of code I've found to debug my program, I totally understand some of them while some others are still mysterious to me.

Here are the two I can't figure out how their logic works.

1. The trie logic

So here's my struct for the trie I've used for this pset:

//dictionary.h

typedef struct node
{
    bool is_word;
    struct node* children[27];
}
node;

I think nearly everybody coding a trie for this pset wrote this down as CS50's walkthrough gave this clue.

In dictionary.c, I use this struct as it follows:

if (isalpha(letter))
{
    if (newptr->children[letter - 'a'] == NULL)
    {
        newptr->children[letter - 'a'] = (struct node*) malloc(sizeof(node));
    }
    newptr = newptr->children[letter - 'a'];
}

Before this part of the code, here's my pseudo:

GLOBAL VARIABLE
create a node* called "root"

------------------------------------------------------------------------------

bool load(const char* dictionary)

open and read dictionary

malloc space memory for the root node
get each character in the dictionary

put the caracter in a "word" array and get to the next character
repeat this until the end of the word

  if the word is finished
  add \n to the last slot of the array "word"

  create a node* called "newptr" to be equal to "root".

    for each character written in "word" array
    char "letter" equals the ith letter of the array "word"

    if (isalpha(letter))
    {
        if (newptr->children[letter - 'a'] == NULL)
        {
            newptr->children[letter - 'a'] = (struct node*) malloc(sizeof(node));
        }
        newptr = newptr->children[letter - 'a'];
    }

My code checks here if it's a letter or something else (could be an apostrophe or the end of the word) and then check

newptr->children[letter - 'a'] 

is NULL.

If it is, I allocate enough space memory (size of a node) to

newptr->children[letter - 'a'].

In my head, here's what I visualize:

Step 1 : creation of a node* called "root".
Step 2 : chunk of memory of size of a node allocated to "root". 
Step 3 : creation of a node* called "newptr" equals to "root".

Pause : inside "newptr", there are two parts

        NEWPTR
        Part 1: bool is_word;
        Part 2: struct node* children[27];
        where in children[27] no slot of the array has been filled so far.

Step 4 : checking if the ith position in the children array is filled with a character. 
         NULL: we give to children[27] a chunck of memory of size node.

Pause : we have now "newptr" to look like this

        NEWPTR
        Part 1: bool is_word;
        Part 2: struct node* children[27];

                Inside children[27] of "newptr" we have now room for a new node unnamed yet:

                UNNAMED
                Part 1: bool is_word;
                Part 2: struct node* children[27];

Step 5 : "newptr" node is equal to the children[ith] of "newptr" node.

Pause : How does look "newptr" now? Assume "letter" is a 'b' so we have 'b' - 'a' = 98 - 97 = 1.

        NEWPTR
        Part 1: bool is_word;
        Part 2: struct node* children[1];
                UNNAMED
                Part 1: bool is_word;
                Part 2: struct node* children[27];

Step 6 : Next letter is a 'i', we start a new loop.
         Checking if the ith position in the children array is filled with a character.
         NULL: we give to children[27] a chunck of memory of size node.

Pause : Visualization of the node "newptr":

        NEWPTR
        Part 1: bool is_word;
        Part 2: struct node* children[1];
                UNNAMED
                Part 1: bool is_word;
                Part 2: struct node* children[27];

                        Inside children[27] of "unnamed" we have now room for a new node also unnamed yet: 

                        UNNAMED
                        Part 1: bool is_word;
                        Part 2: struct node* children[27];

Step 7 : "newptr" node is equal to the children[ith] of "newptr" node.

Pause : How does look "newptr" now? We assumed "letter" is now 'i' so we have 'i' - 'a' = 105 - 97 = 8.

        NEWPTR
        Part 1: bool is_word;
        Part 2: struct node* children[1];
                UNNAMED
                Part 1: bool is_word;
                Part 2: struct node* children[8];
                        UNNAMED
                        Part 1: bool is_word;
                        Part 2: struct node* children[27];

To be fair, this last representation of the three nodes connected to each others doesn't make sense to me. In my code, I don't create new nodes, I only work with the "newptr" node. That makes sense to me for the first node where I assigned the letter 'b' but then, how can I connect this first node to the second for the letter 'i'?

I'm visualizing something like this:

First iteration for the 'b' letter:

NEWPTR
Part 1: bool is_word;
Part 2: struct node* children[1];

Second iteration for the 'i' letter:

NEWPTR
Part 1: bool is_word;
Part 2: struct node* children[8];

instead of

NEWPTR
Part 1: bool is_word;
Part 2: struct node* children[1];
        UNNAMED
        Part 1: bool is_word;
        Part 2: struct node* children[8];

In my mind, there's is a missing

struct node* next;

to connect nodes between each others as we've seen it with the linked list and the programs list-0.c and list-1.c of week 5's second lecture.

How can

struct node* children[27];

can point to the next node?

To me, I can't see how can I link two nodes without declaring a node* "next" in the struct

typedef struct node
{
    bool is_word;
    struct node* children[27];
    struct node* next;
}
node;

To be able then to connect nodes like this:

node* root = (struct node*) malloc(sizeof(node));
node* newptr = (struct node*) malloc(sizeof(node));
newptr->next = NULL;
if (root == NULL)
    root = newptr;
newptr->children['b' - 'a'] = 'b';
node* newptr2 = (struct node*) malloc(sizeof(node));
nexptr->next = newptr2;
newptr2->children['i' - 'a'] = 'i';

When I read

newptr = newptr->children[letter - 'a'];

I guess it's all about recursion but I can't figure out it works step by step.

2. Assigning "letter" to the children[index]

I go back to this chunck of code:

if (isalpha(letter))
{
    if (newptr->children[letter - 'a'] == NULL)
    {
        newptr->children[letter - 'a'] = (struct node*) malloc(sizeof(node));
    }
    newptr = newptr->children[letter - 'a'];
}

and take again the example of the first iteration with "letter" is 'b'.

I do the math at the line

newptr->children[letter - 'a'] == NULL

and find this

newptr->children[98 - 97] == NULL

so

newptr->children[1] == NULL

In this case, it is NULL as nothing is written in the children array. I allocate memory space size of a node to be able to write 'b' at the 2nd position of the children array.

Then, this happens (again):

newptr = newptr->children[1];

How do I know letter 'b' is equals to newptr->children1 ?

Here again in my mind, I'd have imagined more something like this:

letter = newptr->children[1];

When I try to figure this out, I wonder: "When did I store 'b' in "newptr" ?" Because if "newptr" hasn't 'b' stored inside itself, how newptr->children1 can successfully be linked to 'b'?

When I first tried to write this code, the first thing I've written as a global variable was a const char "alphabet" array of size 27 containing the 26 letters and alphabet[26] = '\''

I was thinking that as soon as I've calculated the index of the "children" array, I'll use this same index to map the "alphabet" array and see what letter is stored at the given position to copy it to children[index].

I've never found a correct way to code that and found instead a working bit of code with this method... that I still doesn't get.

3. Conclusion

Long post short (if you've read everything so far, thanks for your time!), this one single line of code is driving me really mad:

newptr = newptr->children[letter - 'a'];

I can feel there's a recursive trick underneath the hood but I can't draw it step by step on a piece of paper.

When I'm stuck, my method is to find a bit of working code somewhere on the internet, comment it line after line to get everything and then re-write the code with my own logic and variable names.

That's what I've done for instance to understand the linked list: I've completely commented code sheets of list-0.c and list-1.c to understand how nodes dynamically behave (insertion, sorting, deletion, etc).

But here, even after fully understanding how linked lists work, I can figure out what's going on in this trie and how it works.

If you have understood my logical issues and got where I'm thinking wrong, please tell me! Thanks.

# EDIT 1 #

I've just watched this video (I shouldn't skip sometimes Zamyla's walkthrough videos...)

Pset 5 Walthrough: Load

When she takes the "fox" example, here's her logic:

f: root->children[5];
o: root->children[5]->children[15]
x: root->children[5]->children[15]->children[23]

Alright, this can make sense to me and I start getting why a

struct node* next;

as used in linked lists is not necessary.

But the question remains: how

newptr (or "root" for Zamyla) = newptr->children[5];

then

newptr = newptr->children[15];

can be equal to

newptr = newptr->children[5]->children[15];

and finally

newptr = newptr->children[23];

can be equal to

newptr = newptr->children[5]->children[15]->children[23];

?

Could someone please explain me how recursion works here? Meanwhile, I'm heading back to my books to read chapters on that topic. If I find anything, I'll post a second edit. Thanks!

# EDIT 2 #

I'VE GOT IT!

Recursion is really tricky but now I see.

Here's my explanation and please, if someone can just say "yes it's correct", it'd lift a weight off my shoulders.

So let's take again Zamyla's fox example (see Edit 1).

Letter after letter, it works like this:

f: root->children[5];
o: root->children[5]->children[15]
x: root->children[5]->children[15]->children[23]

In a code form, using recursion, we write this:

f: root = root->children[5];
o: root = root->children[15];
x: root = root->children[23];

Alright, first loop for 'f' is easy to get: we ask to update itself by assigning the letter 'f' to its pointer children[5].

That means now that root stands for root->children[5].

Let's move on 'o' and compare Zamyla's path to ours:

Zamyla
o: root->children[5]->children[15]

Us
o: root = root->children[15];

At first sight, the part for 'f' is gone in our version. When we think back, we said that root was a shortcut for root->children[5] meaning that we can replace root in our code like this:

root = root->children[5]
^^^^   *****************

o: root = root->children[15]
          ^^^^
        = root->children[5]->children[15]
          *****************

and now root stands for root->children[5]->children[15]

Last recursion for 'x':

root = root->children[5]->children[15]
^^^^   *******************************

x: root = root->children[23]
          ^^^^
        = root->children[5]->children[15]->children[23]
          *******************************

Now, root stands for root->children[5]->children[15]->children[23], the three nodes of "fox".

I should have been more mathematical to understand how recursion was working. As soon as you replace the name root its value, everything makes sense!

I hope this will eventually help someone else.

# FINAL EDIT #

Here again, we're taking Zamyla's "fox" example:

f: root->children[5];

and we compare this logic to this chunck of code:

if (isalpha(letter))
{
    if (newptr->children[letter - 'a'] == NULL)
    {
        newptr->children[letter - 'a'] = (struct node*) malloc(sizeof(node));
    }
    newptr = newptr->children[letter - 'a'];
}

OK so let's pass the letter 'f'. First, the if condition: is 'f' a letter? Yes it is so let's go inside. When we do the math, we find that

newptr->children[letter - 'a']
=
newptr->children[5]

We allocate memory space to the pointer children[5] of its size: node.

Once there, we have this:

newptr = newptr->children[5];

First of all, Cliff B mentionned in a post below something very important: for the first node, we need a root for our trie. If we lose the first node of the trie, we lose everything!

To avoid such a disaster, it's important to save this first node, let's call it "root" here and then, only use one temporary pointer, "newptr", to build the trie. To be sure to not meet any problem with our trie, let's amend this line of code:

newptr = root->children[5];

Alright so now let's figure out why root->children[5] refers to 'f' even if 'f' or letter is not explicitly mentionned in this line of code.

Well, here's my tip to help yourself with pointer (at least in this case, pointers are tricky).

children[5] is a pointer of type node* and that's why we use a -> instead of a .. So at the end, after making sure 'f' is a letter and we have allocated enough memory space, we end up with this result: "newptr" can be found at this address: root->children[5].

Let's take now the process backward and assume that we read the result first: newptr = root->children[5]. How we made it to that result? Maybe we needed to allocate memory space, maybe not. But there's one thing that is absolutely unavoidable to get to this result: the if condition must verify that letter is a 'f' and not any other letter.

As we use the same mathematical method to find the index of "children", index 5 can only refers to 'f'. If we pass a number in the if condition, the condition is not verified and no node will be created. If we pass the letter 'c', we'll do the math and find out that children's index is 2. Every single argument that pass successfully the if condition will get one unique index, from 0 to 26.

That's how now I consider the logic: instead of looking for where 'f' has been told to be assigned to root->children[5], better understand how root->children[5] made it to exist.

I think my explanation isn't a top answer but still, I hope it'll help someone who one day lost him/herself in this same logical maze.

Answer 1

Your understanding is correct, but your example has a dangerous flaw if you were to implement it. Look back at your question as a whole. You have two important variables, root and newptr. root is the pointer that actually points to, well, the literal root of the trie. It's critical that you never reassign this pointer. If you do, you'll lose the root of the trie!

Next, newptr is another pointer to nodes. It can be set to point to root or to any other node in the trie! This is your floater, your temoporary pointer that will let you traverse down the tree to either load or check for a word. In your Edit #2, you'd use it like this:

f: newptr = root->children[5];       
o: newptr = newptr->children[15];   // = root->children[5]->children[15]
x: newptr = newptr->children[23];   // = root->children[5]->children[15]->children[23]

So, you use a temporary pointer, such as newptr, to traverse along the trie while maintaining root as the permanent starting point.

BTW, your very detailed explanation looked fine to me, with one exception. In your pseudocode, you mentioned adding '\n' to the end of the string that holds the word you just got from the dictionary file, one character at a time. However, you made no mention of adding an end of string marker, \0 to the end of the string. Also, what purpose will inserting the '\n' into the string serve?

So, yes, you've pretty much got it. ;-)