I tried using the struct shown as described in the lecture but it come up with a problem.

    typedef struct node
        bool is_word;
            struct node* address[27];

using this struct if you have two word in a files such as vu and vo but vu is the only one in the dictionary it will say both are in the dictionary because when you load vu it will change is_word to true so when you check vu it says that is ok as well. or have I totally mis_understood the use of the struct

  • Your question depends on how you implemented load and check. For instance, a word with two letters will require the root node and two letter nodes deep after that. The bool on the last node will tell if traversing those nodes spells a word. I'm guessing that you're setting the is_word one node too early and don't have the word spelled out fully. As you are loading a word, for each letter,you will either allocate or move to a new node, or set is_word to true. If this doesn't help, plz post the relevant load and check code.
    – Cliff B
    May 8, 2015 at 17:17
  • many thanks for replying to my question
    – biggrey54
    May 15, 2015 at 12:20

1 Answer 1


Not really. If you have allocate memory for a node that represents the letter 'v' as the first letter of a word, then according to the implementation, this node has an array of node children each of which represents a letter that comes right after 'v' in that word. For example:

#define SIZE 26

typdef struct node
    bool isWord;
    struct node *children[SIZE];
} node;

// the starting letters
node *root[SIZE] = {0};

// calculate the index of the node that represents the 'v'
int vIndex = 'v' - 'a';
// allocate memory for node that represents 'v' as the first letter of a word
root[vIndex] = malloc(sizeof(node));

Now allocating memory for any of the following nodes would correspond having the corresponding letter as a second letter in a word that follows a 'v'. So allocating memory for

root[vIndex]->children['a' - 'a']; // corresponds the 'a' in "va"
root[vIndex]->children['b' - 'a']; // corresponds the 'b' in "vb"
root[vIndex]->children['z' - 'a']; // corresponds the 'z' in "vz"

So if I want to have the word "van" loaded, assuming root[vIndex] have memory allocated for it (as I did above), I could do

// calculate the index for the 'a'
int aIndex = 'a' - 'a';
root[vIndex]->children[aIndex] = malloc(sizeof(node));
// calculate the index for the 'n'
int nIndex = 'n' - 'a';
root[vIndex]->children[aIndex]->children[nIndex] = malloc(sizeof(node));

// mark the end of the word
root[vIndex]->children[aIndex]->children[nIndex]->isWord = true;

And there you have the word "van" loaded into the try except that the code above looks awful. So is there a more elegant way we could do that? Certainly.

First, we could use a loop to iterate over each character in our word. We may use a loop for that. Then we may use a single variable to calculate the index inside the loop (i.e., the index of the current character) and we could use a temporary node to keep track of the current node. Here's some pseudocode:

1. declare a string called word and set it to "van"

2. declare a variable called index and set it to word[0] - 'a'
// ensure memory is allocated only once for any root node
3. if root[index] doesn't have memory allocated for it
    4. allocate memory for root[index]
5. declare a variable called current and set it to root[index]
6. for each character in word starting with the second character
    7. calculate the index of the current character and assign it to index
    // ensure memory is allocated only once for the same node
    8. if current->children[index] doesn't have memory allocated for it
        9. allocate memory for current->children[index]
      // update current
    10. set current to current->children[index]

// mark the end of the word
11. set current->isWord to true
  • I wrote the pseudocode above on the fly. Please forgive me if there are any logical errors!
    – kzidane
    May 8, 2015 at 18:23
  • Kareem is right. Exactly what I had in mind, but I wanted to see what you were thinking and go from there before laying out the whole explanation. :-)
    – Cliff B
    May 8, 2015 at 19:19
  • many thanks to you for answering my question and it really helped to understand what I wanted to do
    – biggrey54
    May 15, 2015 at 12:20
  • @biggrey54, you may up-vote the answer and accept it to mark your question as solved! Thanks!
    – kzidane
    May 15, 2015 at 14:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .