Insert
Lesson 5 of 14 in Coddy's Tries - Data Structures Series #8 course.
To insert a word into the trie, walk down from the root one character at a time. For each character of the word: if the current node has no child for that character, create a new TrieNode and attach it. Either way, move into that child and continue with the next character.
When you reach the end of the word, mark the node you landed on with isEndOfWord = true. That flag is what later distinguishes a real stored word from a path that just happens to exist because it is a prefix of something else.
Inserting "cat" and then "car" shares the c -> a path and only branches at the third character. That sharing is what makes tries so space-efficient for dictionaries.
Challenge
EasyAdd a method insert to the Trie class.
It gets a string word and stores it in the trie:
- Start at the
root. For each charactercinword, if the current node has no child forc, add a newTrieNodethere. - Move into that child and continue.
- After the last character, mark the final node's
isEndOfWordastrue.
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); }
}
return 0;
}