CODEWITHSUNDEEP
ctraversaltrie
Jake Psimos
Jake Psimos

Reputation: 640

Printing words in a trie in C

Populating the trie is no problem. Words contain no numbers or spaces and only lower case letters.

printTrieContents uses a buffer malloced in main.

THE PROBLEM: if the trie contains the words "scores" and "something", "scores" will be printed but "something" will not.

Everything else is okay.

struct trieNode {
  int count;
  struct trieNode *children[ALPHA_SIZE];
};


void printTrieContents(struct trieNode *root, char *buffer, int buffIndex){
        int i;
        for(i = 0; i < ALPHA_SIZE; i++){
                if(root->children[i] != NULL){
                        buffer[buffIndex] = i + 'a';
                        printTrieContents(root->children[i], buffer, buffIndex + 1);
                }
                if(!hasChildren(root)){
                        buffer[buffIndex] = '\0';
                        if(strlen(buffer) > 0){
                                printf("%s: %d\n", buffer, root->count);
                                buffIndex = 0;
                        }
                }   
        }
}

int hasChildren(struct trieNode *root){
        int i;
        for(i = 0; i < ALPHA_SIZE; i++){
                if(root->children[i] != NULL){
                        return 1;
                }
        }
return 0;
}

Upvotes: 0

Views: 1238

Answers (1)

Walter Delevich
Walter Delevich

Reputation: 427

You eventually traverse to a leaf. At this point, being a leaf, you have no children. you affix null and set buffIndex to zero. You don't exit though, you keep spinning, meaning you'll go back into that clause and set buffer[0] to Null, effectively clearing your string, you'll eventually recurse back up and move on to the next child.

edit: When you detect that you need to affix the null, instead of setting buffIndex ( note, buffIndex is local to the current frame, setting it won't have any affect on the rest of your call stack) return. You'll begin recursing back up your stack. Then you'll get back to a frame that has more children, and you can begin iterating over other children, overwriting buffer with their new string, and printing new words.

Upvotes: 1

Related Questions