A Trie (pronounced "try"), also called a prefix tree or digital tree, is a specialized tree-based data structure used for efficient string storage and retrieval. Each node represents a character, and paths from root to leaf form complete words. Tries excel at prefix-based searches, autocomplete, and spell checking applications.
Unlike binary search trees, tries don't store entire keys at nodes. Instead, each level represents a character position, and words are formed by traversing from root to nodes marked as "end of word". This structure enables O(m) search time where m is the word length, regardless of how many words are stored.
Insert Word: Enter a word and click "Insert Word" to add it character by character.
Search Word: Enter a complete word to check if it exists in the trie (highlights path).
Find Prefix: Enter a prefix to see all words that start with those characters.
Delete Word: Remove a word from the trie (removes unused nodes).
Visual Indicators: Root node (*) in purple, end-of-word nodes in green with a dot marker.
Load Sample: Click to add example words: cat, car, card, care, dog, door.
Insertion: Start at root, for each character create node if it doesn't exist, traverse down. Mark last node as end of word.
Search: Traverse from root following characters. Word exists if path exists AND last node is marked as end of word.
Prefix Search: Navigate to prefix's last character, then collect all words in that subtree using DFS.
Deletion: Mark end-of-word as false, remove nodes if they have no children and aren't part of other words.
Time Complexity: All operations are O(m) where m is the word/prefix length.
Space Complexity: O(ALPHABET_SIZE * N * M) where N is number of words, M is average length.
Autocomplete: Search engines, IDE code completion, phone keyboards showing word suggestions.
Spell Checkers: Dictionary lookups and suggesting corrections for misspelled words.
IP Routing: Longest prefix matching in network routers for efficient packet forwarding.
Contact Search: Phone apps searching contacts by name prefix as you type.
Word Games: Scrabble, Boggle validators checking if letter combinations form valid words.
T9 Predictive Text: Old phone keyboards predicting words from number sequences.
vs Hash Table: Tries support prefix operations and ordered traversal; hash tables are faster for exact lookups.
vs BST: Tries have consistent O(m) time; BST time depends on tree balance O(log n) to O(n).
Space Usage: Tries use more memory but share common prefixes; effective for large datasets with overlapping prefixes.
Best Use Case: When you need prefix searches, autocomplete, or lexicographic ordering of strings.
Insert: Create nodes for each character, mark end of word - O(m).
Search: Traverse path checking each character exists - O(m).
Starts With: Check if prefix path exists (don't require end marker) - O(m).
Delete: Remove end marker, optionally clean up unused nodes - O(m).
Autocomplete: Find prefix node, then DFS to collect all words in subtree.
Count Words: DFS counting nodes marked as end of word.
Implement Trie: Node with children map/array and isEnd flag; insert/search/startsWith methods.
Word Search II: Build trie from words, DFS on board with trie navigation for efficient pruning.
Longest Common Prefix: Insert all words, find longest path where each node has exactly one child.
Replace Words: Build trie of roots, for each word find shortest matching prefix.
Search Suggestions: Navigate to prefix, DFS with priority queue for top k lexicographic matches.
Add and Search Word: Handle '.' wildcard by trying all children at that position.
Maximum XOR: Build trie of binary representations, greedily choose opposite bits.
/* Trie implementation in C */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define ALPHABET_SIZE 26
typedef struct TrieNode {
struct TrieNode* children[ALPHABET_SIZE];
bool isEndOfWord;
} TrieNode;
TrieNode* createNode() {
TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
node->isEndOfWord = false;
for (int i = 0; i < ALPHABET_SIZE; i++)
node->children[i] = NULL;
return node;
}
void insert(TrieNode* root, const char* word) {
TrieNode* curr = root;
for (int i = 0; word[i]; i++) {
int index = word[i] - 'a';
if (!curr->children[index])
curr->children[index] = createNode();
curr = curr->children[index];
}
curr->isEndOfWord = true;
}
bool search(TrieNode* root, const char* word) {
TrieNode* curr = root;
for (int i = 0; word[i]; i++) {
int index = word[i] - 'a';
if (!curr->children[index]) return false;
curr = curr->children[index];
}
return curr && curr->isEndOfWord;
}
bool startsWith(TrieNode* root, const char* prefix) {
TrieNode* curr = root;
for (int i = 0; prefix[i]; i++) {
int index = prefix[i] - 'a';
if (!curr->children[index]) return false;
curr = curr->children[index];
}
return true;
}
int main() {
TrieNode* root = createNode();
insert(root, "cat"); insert(root, "car");
insert(root, "card"); insert(root, "care");
printf("search 'car': %d\n", search(root, "car")); // 1
printf("search 'ca': %d\n", search(root, "ca")); // 0
printf("startsWith 'ca': %d\n", startsWith(root, "ca")); // 1
return 0;
}