WordCount
Lesson 9 of 14 in Coddy's Tries - Data Structures Series #8 course.
How many distinct words live in this trie right now? There is no running counter, so we have to walk the tree and count the nodes where isEndOfWord is true.
A depth-first search starting at the root does the job in one pass. For each node, add 1 if it is end-of-word, then recurse into every child and sum the results. The total is the number of stored words.
Notice this naturally handles duplicates: inserting "cat" three times still marks one node as end-of-word, so the count is 1. Prefixes that were never inserted in their own right are not counted either - their nodes exist, but isEndOfWord is false on them.
Challenge
EasyAdd a method wordCount to the Trie class.
It takes no input and returns the number of distinct words currently stored in the trie. Walk the trie from the root and count every node whose isEndOfWord is true.
Try it yourself
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"
int main() {
Trie t;
Trie_init(&t);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
if (strcmp(cmd, "search") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_search(&t, arg) ? "true" : "false"); }
if (strcmp(cmd, "startsWith") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_startsWith(&t, arg) ? "true" : "false"); }
if (strcmp(cmd, "delete") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_delete(&t, arg); }
if (strcmp(cmd, "wordCount") == 0) { printf("%d\n", Trie_wordCount(&t)); }
}
return 0;
}