Trouble with Substrings in Check in Pset5

Question

I have used a trie structure to implement my dictionary in pset5 and I believe my load() function is operating correctly, however I seem to be having trouble with checking substrings in the check() function (e.g. it finds cat, but not caterpillar). This was pointed out to me by check50, however I can't workout where the failure to validate the word is coming from. My code otherwise passes check50 except for the substrings check. From what I've seen in gdb, I believe the isWord value in my trie is updating correctly in load(), but isn't being 'found' correctly by check().

---

EDIT: I have run valgrind on my code and am starting to understand its output a little more. It was telling me there were errors regarding undefined variables for the isWord boolean, so I have now added that fix to my code (not shown here), however I have noticed something even more strange. I ran a bit of test code to see how large my node struct is, and it is apparently 224 bytes. If I were to run this code on the large dictionary (143091 words), I believe my trie should be a minimum of 35 million bytes (assuming 1 alloc per word, but of course there will be more than this, hence why I say a minimum). However, according to valgrind it is nowhere near this size, clocking in at 20,384 bytes and saying that there has been 91 allocs. This is massively under what I should be getting, so what could be the reason for this? This is especially concerning for me as my code seems to pass most of the check50 checks. This is now leading me to think that there may be an error in my load() function instead (or perhaps as well as) my check() function.

Here is my code:

bool load(const char* dictionary)
{
    // open dictionary file
    FILE* dict = fopen(dictionary, "r");
...        
    // allocate memory for root node
    root = malloc(sizeof(node));
...            
    // set traversal node to point at root node for now
    traversal = root;

    // start iterating over letters and putting them in the trie structure
    for (char c = fgetc(dict); c != EOF; c = fgetc(dict))
    {

        // if it is a letter
        if (isalpha(c)) // could write (c > 'a' && c < 'z'), might aid optimization??
        {
            // checks if node is NULL
            if (traversal->child[c - 'a'] == NULL)
            {
                // if NULL, malloc a new node
                traversal->child[c - 'a'] = malloc(sizeof(node));

                // move traversal node down trie for next letter
                traversal = traversal->child[c - 'a'];
...              
            }
        }
        else if ( c == '\'') // if c is apostrophe character
        {
            // checks if node is NULL
            // this could be integrated into the elseif statement above for efficiency??
            if (traversal->child[26] == NULL)
            {
                // if NULL, malloc a new node
                traversal->child[26] = malloc(sizeof(node));

                // move traversal node down trie for next letter
                traversal = traversal->child[26];
...
            }
        }
        else if ( c == '\n') // if word has been completed and we have newline character
...
    }

...

    // if all is good
    return true;
}

Answer 1

So I found the problem. There was no condition in the code to 'move down a layer' so to speak if there was a node. I was just checking for the negative, rather than the affirmative. Code changed and checked, and it now matches the staff output exactly and passes check50! As I now have a solution, I shall edit out parts of the code to comply with the academic honesty policy.