Delete Word from 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
struct TrieNode {
struct TrieNode* children[CHAR_SIZE];
bool isEndOfWord;
};
struct TrieNode* createNode() {
struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode));
node->isEndOfWord = false;
for (int i = 0; i < CHAR_SIZE; i++) node->children[i] = NULL;
return node;
}
void insert(struct TrieNode* root, const char* word) {
while (*word) {
int index = *word - 'a';
if (!root->children[index]) root->children[index] = createNode();
root = root->children[index];
word++;
}
root->isEndOfWord = true;
}
bool search(struct TrieNode* root, const char* word) {
while (*word) {
int index = *word - 'a';
if (!root->children[index]) return false;
root = root->children[index];
word++;
}
return root != NULL && root->isEndOfWord;
}
bool deleteWord(struct TrieNode* root, const char* word, int depth) {
if (!root) return false;
if (word[depth] == '\0') {
if (!root->isEndOfWord) return false;
root->isEndOfWord = false;
for (int i = 0; i < CHAR_SIZE; i++)
if (root->children[i]) return false;
return true;
}
int index = word[depth] - 'a';
if (deleteWord(root->children[index], word, depth + 1)) {
free(root->children[index]);
root->children[index] = NULL;
return !root->isEndOfWord && !search(root, word);
}
return false;
}
int main() {
struct TrieNode* root = createNode();
insert(root, "apple");
insert(root, "app");
deleteWord(root, "apple", 0);
printf("apple: %d\n", search(root, "apple")); // 0 (false)
printf("app: %d\n", search(root, "app")); // 1 (true)
return 0;
}
Time Complexity
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(n) | In the best case, the algorithm still traverses each character of the word once, resulting in linear time complexity relative to the word length. |
Average Case | O(n) | On average, the algorithm traverses n nodes (one for each character of the word) and performs constant-time operations at each node, leading to O(n) time. |
Worst Case | O(n) | In the worst case, the algorithm traverses down the full length of the word and may also backtrack up to remove unnecessary nodes, still bounded by O(n). |
Comments
Loading comments...