Trie Insert and Search
In this page:
Insert Operation
Inserting a word walks character by character from the root, creating a new child node whenever the needed character link doesn't already exist, and finally marks the last node reached as the end of a complete word.
Example: Insert Operation
#include <iostream>
#include <unordered_map>
using namespace std;
struct Node { unordered_map<char,Node*> children; bool isEnd=false; };
Node* root = new Node();
void insert(string word) {
Node* cur = root;
for (char c : word) {
if (!cur->children.count(c)) cur->children[c] = new Node();
cur = cur->children[c];
}
cur->isEnd = true;
}
int main() { insert("cat"); cout << "'cat' inserted, new node created for each missing character link"; return 0; }import java.util.*;
public class Main {
static class Node { Map<Character,Node> children = new HashMap<>(); boolean isEnd = false; }
static Node root = new Node();
static void insert(String word) {
Node cur = root;
for (char c : word.toCharArray()) {
cur.children.putIfAbsent(c, new Node());
cur = cur.children.get(c);
}
cur.isEnd = true;
}
public static void main(String[] args) {
insert("cat");
System.out.println("'cat' inserted, new node created for each missing character link");
}
}class Node:
def __init__(self):
self.children = {}
self.is_end = False
root = Node()
def insert(word):
cur = root
for ch in word:
if ch not in cur.children:
cur.children[ch] = Node()
cur = cur.children[ch]
cur.is_end = True
insert("cat")
print("'cat' inserted, new node created for each missing character link")#include <stdio.h>
struct Node { struct Node* children[26]; int isEnd; };
struct Node nodes[100]; int nodeCount = 1;
void insert(char* word) {
int cur = 0;
for (int i = 0; word[i]; i++) {
int idx = word[i]-'a';
if (!nodes[cur].children[idx]) { nodes[cur].children[idx] = &nodes[nodeCount]; nodeCount++; }
}
}
int main() {
insert("cat");
printf("'cat' inserted, new node created for each missing character link");
return 0;
}Login to try C/C++/Java code in the editor
Search Operation
Searching for a word follows the exact same character-by-character path through existing links; if any required link is missing partway through, or the final node isn't marked as a word-end, the search correctly reports the word isn't present.
Example: Search Operation
#include <iostream>
#include <unordered_map>
using namespace std;
struct Node { unordered_map<char,Node*> children; bool isEnd=false; };
Node* root = new Node();
bool search(string word) {
Node* cur = root;
for (char c : word) {
if (!cur->children.count(c)) return false;
cur = cur->children[c];
}
return cur->isEnd;
}
int main() { cout << (search("cat") ? "found" : "not found, missing link or isEnd not set"); return 0; }import java.util.*;
public class Main {
static class Node { Map<Character,Node> children = new HashMap<>(); boolean isEnd = false; }
static Node root = new Node();
static boolean search(String word) {
Node cur = root;
for (char c : word.toCharArray()) {
if (!cur.children.containsKey(c)) return false;
cur = cur.children.get(c);
}
return cur.isEnd;
}
public static void main(String[] args) {
System.out.println(search("cat") ? "found" : "not found, missing link or isEnd not set");
}
}class Node:
def __init__(self):
self.children = {}
self.is_end = False
root = Node()
def search(word):
cur = root
for ch in word:
if ch not in cur.children:
return False
cur = cur.children[ch]
return cur.is_end
print("found" if search("cat") else "not found, missing link or is_end not set")#include <stdio.h>
struct Node { struct Node* children[26]; int isEnd; };
struct Node nodes[100]; int nodeCount = 1;
int search(char* word) {
int cur = 0;
for (int i = 0; word[i]; i++) {
int idx = word[i]-'a';
if (!nodes[cur].children[idx]) return 0;
}
return nodes[cur].isEnd;
}
int main() { printf(search("cat") ? "found" : "not found, missing link or isEnd not set"); return 0; }Login to try C/C++/Java code in the editor
Prefix Search
A prefix can exist in the trie — meaning some stored word starts with it — even if that prefix itself was never inserted as a complete word; the difference is simply whether the final node reached is marked as a word-end or not.
Example: Prefix Search
#include <iostream>
using namespace std;
int main() {
bool prefixCa_reachable = true, prefixCa_isWord = false;
cout << "'ca' reachable=" << prefixCa_reachable << " but never inserted as a full word, isEnd=" << prefixCa_isWord;
return 0;
}public class Main {
public static void main(String[] args) {
boolean prefixReachable = true, prefixIsWord = false;
System.out.println("'ca' reachable=" + prefixReachable + " but never inserted as a full word, isEnd=" + prefixIsWord);
}
}prefix_reachable, prefix_is_word = True, False
print(f"'ca' reachable={prefix_reachable} but never inserted as a full word, is_end={prefix_is_word}")#include <stdio.h>
int main() {
int prefixReachable = 1, prefixIsWord = 0;
printf("'ca' reachable=%d but never inserted as a full word, isEnd=%d", prefixReachable, prefixIsWord);
return 0;
}Login to try C/C++/Java code in the editor
Complexity
Both insertion and search only ever touch as many nodes as the word has characters, so each operation runs in O(L) time where L is the word's length, completely independent of how many other words are stored in the trie.
Example: Complexity
#include <iostream>
using namespace std;
int main() {
cout << "Insert and search: O(L) where L = word length, independent of how many other words are stored";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Insert and search: O(L) where L = word length, independent of how many other words are stored");
}
}print("Insert and search: O(L) where L = word length, independent of how many other words are stored")#include <stdio.h>
int main() {
printf("Insert and search: O(L) where L = word length, independent of how many other words are stored");
return 0;
}Login to try C/C++/Java code in the editor
Practical Uses
This makes tries a natural fit for autocomplete (walk to a prefix's node, then explore everything beneath it) and dictionary lookups where you need fast, exact membership and prefix checks.
Example: Practical Uses
#include <iostream>
using namespace std;
int main() {
cout << "Autocomplete: walk to a prefix's node, then explore everything beneath it";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Autocomplete: walk to a prefix's node, then explore everything beneath it");
}
}print("Autocomplete: walk to a prefix's node, then explore everything beneath it")#include <stdio.h>
int main() {
printf("Autocomplete: walk to a prefix's node, then explore everything beneath it");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 7 topics to unlock
0/7 topics done
Complete these topics first: