Trie (Prefix Tree)
Definition
A Trie (pronounced “try”) is a tree-like data structure used efficiently for storing strings. Each node represents a character of a string.
How it Works
Instead of storing a whole word like “Apple” in one node, a Trie breaks it down.
- The root is empty.
- The first child is ‘A’.
- The child of ‘A’ is ‘p’, and so on.
- Words with common prefixes (like “Car” and “Cat”) share the same initial path (‘C’ rightarrow ‘a’).
Real-World Analogy:
Think of auto-complete on your phone. When you type “H-E-L”, the phone looks down the path of those specific letters to suggest “Hello” or “Help”. It doesn’t look at words starting with ‘Z’.
Example
Insert: “CAT”, “CAR”
Structure:
Both words share the ‘C-A’ path.
Code Example
PythonJavaCC++
# Trie Node
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
# Insert word into Trie
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
# Search word
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
import java.util.HashMap;
class TrieNode {
HashMap<Character, TrieNode> children = new HashMap<>();
boolean isEndOfWord = false;
}
class Trie {
TrieNode root = new TrieNode();
// Insert word
void insert(String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
node.children.putIfAbsent(ch, new TrieNode());
node = node.children.get(ch);
}
node.isEndOfWord = true;
}
// Search word
boolean search(String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
if (!node.children.containsKey(ch))
return false;
node = node.children.get(ch);
}
return node.isEndOfWord;
}
}
#include <stdio.h>
#include <stdlib.h>
#define ALPHABET_SIZE 26
// Trie Node
struct TrieNode {
struct TrieNode* children[ALPHABET_SIZE];
int isEndOfWord;
};
// Create node
struct TrieNode* createNode() {
struct TrieNode* node =
(struct TrieNode*)malloc(sizeof(struct TrieNode));
node->isEndOfWord = 0;
for (int i = 0; i < ALPHABET_SIZE; i++)
node->children[i] = NULL;
return node;
}
// Insert word
void insert(struct TrieNode* root, char* word) {
struct TrieNode* node = root;
for (int i = 0; word[i] != '\0'; i++) {
int index = word[i] - 'a';
if (!node->children[index])
node->children[index] = createNode();
node = node->children[index];
}
node->isEndOfWord = 1;
}
// Search word
int search(struct TrieNode* root, char* word) {
struct TrieNode* node = root;
for (int i = 0; word[i] != '\0'; i++) {
int index = word[i] - 'a';
if (!node->children[index])
return 0;
node = node->children[index];
}
return node->isEndOfWord;
}
#include <iostream>
#include <unordered_map>
using namespace std;
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
bool isEndOfWord = false;
};
class Trie {
public:
TrieNode* root;
Trie() {
root = new TrieNode();
}
// Insert word
void insert(string word) {
TrieNode* node = root;
for (char ch : word) {
if (node->children.count(ch) == 0)
node->children[ch] = new TrieNode();
node = node->children[ch];
}
node->isEndOfWord = true;
}
// Search word
bool search(string word) {
TrieNode* node = root;
for (char ch : word) {
if (node->children.count(ch) == 0)
return false;
node = node->children[ch];
}
return node->isEndOfWord;
}
};
Complexity Analysis
- Time Complexity: O(L) where L is the length of the word. Searching for a word depends only on the word’s length, not the size of the database!
- Space Complexity: O(N times L) in worst case, but saves space when many words share prefixes.
Use Cases
- Autocomplete/Typeahead: Google search suggestions.
- Spell Checkers: Validating if a word exists in the dictionary.
- IP Routing: Longest prefix matching in internet routers.