Given a Trie (prefix tree), insert a word into it. A Trie is used to efficiently store and retrieve strings, especially useful for prefix-based searches. The objective is to add the given word into the Trie character by character such that each character leads to a node, and the final character marks the end of the word.
Insert Word in Trie - Visualization
Visualization Player
Problem Statement
Examples
Solution
Algorithm Steps
Code
C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define CHAR_SIZE 26
typedef struct TrieNode {
struct TrieNode *children[CHAR_SIZE];
bool is_end_of_word;
} TrieNode;
TrieNode* createNode() {
TrieNode *node = (TrieNode*)malloc(sizeof(TrieNode));
node->is_end_of_word = false;
for (int i = 0; i < CHAR_SIZE; i++) node->children[i] = NULL;
return node;
}
void insert(TrieNode *root, const char *word) {
TrieNode *node = root;
while (*word) {
int index = *word - 'a';
if (!node->children[index]) node->children[index] = createNode();
node = node->children[index];
word++;
}
node->is_end_of_word = true;
}
int main() {
TrieNode *root = createNode();
insert(root, "code");
insert(root, "coder");
insert(root, "coding");
printf("Inserted words into Trie\n");
return 0;
}
Time Complexity
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(n) | In the best case, the algorithm still needs to traverse all n characters of the input word to insert it into the Trie, even if all nodes already exist. |
Average Case | O(n) | On average, the algorithm traverses and possibly creates n new nodes for a word of length n. Each character requires a constant-time operation. |
Worst Case | O(n) | In the worst case, none of the characters exist in the Trie, so the algorithm creates a new node for each of the n characters in the input word. |
Comments
Loading comments...