Trie (Prefix Tree)
Last updated
A trie (pronounced "try"), or prefix tree, stores a set of strings by their characters: each edge is labeled with a character, and a path from the root spells out a prefix. Words that share a prefix share the same nodes, so "car", "card", and "care" all reuse the c-a-r path. Press play above to watch words get inserted one character at a time, branching only where they differ.
Because lookups walk one node per character, searching for a word of length m takes O(m) time regardless of how many words the trie holds. That makes tries ideal for autocomplete, spell-checking, and prefix search.
Time & space complexity
| Operation | Complexity | Notes |
|---|---|---|
| Insert | O(m) | m = length of the word |
| Search | O(m) | One step per character |
| Prefix query | O(m) | Walk to the prefix node |
| Space | O(total chars) | Shared prefixes stored once |
Step by step (insert)
| Step | What happens |
|---|---|
| 1 | Start at the root node. |
| 2 | For each character in the word, look for a matching child edge. |
| 3 | If it exists, follow it (reusing the shared prefix). |
| 4 | If not, create a new child node for that character. |
| 5 | After the last character, mark that node as end-of-word. |
Worked example
Inserting ["car", "card", "care"] into an empty trie:
| Step | Structure | Action |
|---|---|---|
Insert car | root → c → a → r✓ | No matching children exist, so create c, a, r and mark r as end-of-word. |
Insert card | root → c → a → r✓ → d✓ | Reuse the existing c-a-r path, then create one new child d and mark it end-of-word. |
Insert care | root → c → a → r✓ → {d✓, e✓} | Reuse c-a-r, branch off r with a new child e, and mark e end-of-word. |
Search care | root → c → a → r → e✓ | Walk c, a, r, e; the final node is marked end-of-word, so care is present. |
Search ca | root → c → a | The path exists but a is not marked end-of-word, so ca is a prefix but not a stored word. |
When to use a trie
| Use it when | Avoid it when |
|---|---|
| You need prefix queries or autocomplete over a set of strings. | You only need whole-key lookups - a hash table is faster and lighter. |
| Many stored words share common prefixes, so nodes are reused. | Keys are long and rarely overlap, wasting one node per character. |
| You want keys returned in sorted order via traversal. | Memory is tight - per-node child pointers add significant overhead. |
| Lookup cost must depend on key length, not dataset size. | The alphabet is huge (e.g. full Unicode) and children are stored densely. |
Trie (Prefix Tree) code
A clean, runnable Trie (Prefix Tree) implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Trie (Prefix Tree) code in Python
Python
1class TrieNode:2 def __init__(self):3 self.children = {}4 self.is_word = False5
6
7class Trie:8 def __init__(self):9 self.root = TrieNode()10
11 def insert(self, word):12 node = self.root13 for ch in word:14 node = node.children.setdefault(ch, TrieNode())15 node.is_word = True16
17 def search(self, word):18 node = self._walk(word)19 return node is not None and node.is_word20
21 def starts_with(self, prefix):22 return self._walk(prefix) is not None23
24 def _walk(self, s):25 node = self.root26 for ch in s:27 if ch not in node.children:28 return None29 node = node.children[ch]30 return node31
32
33trie = Trie()34for word in ["car", "card", "care", "dog"]:35 trie.insert(word)36
37print("search(card): ", trie.search("card"))38print("search(ca): ", trie.search("ca"))39print("starts_with(ca): ", trie.starts_with("ca"))40print("starts_with(do): ", trie.starts_with("do"))41print("starts_with(cat): ", trie.starts_with("cat"))Trie (Prefix Tree) code in JavaScript
JavaScript
1class TrieNode {2 constructor() {3 this.children = {};4 this.isEnd = false;5 }6}7
8class Trie {9 constructor() {10 this.root = new TrieNode();11 }12
13 insert(word) {14 let node = this.root;15 for (const ch of word) {16 if (!node.children[ch]) node.children[ch] = new TrieNode();17 node = node.children[ch];18 }19 node.isEnd = true;20 }21
22 // Walk the prefix; null when a character is missing23 findNode(prefix) {24 let node = this.root;25 for (const ch of prefix) {26 node = node.children[ch];27 if (!node) return null;28 }29 return node;30 }31
32 search(word) {33 const node = this.findNode(word);34 return node !== null && node.isEnd;35 }36
37 startsWith(prefix) {38 return this.findNode(prefix) !== null;39 }40}41
42const trie = new Trie();43for (const word of ["car", "card", "care", "dog"]) trie.insert(word);44console.log("search(\"card\"):", trie.search("card"));45console.log("search(\"ca\"):", trie.search("ca"));46console.log("startsWith(\"ca\"):", trie.startsWith("ca"));Trie (Prefix Tree) code in Java
Java
1public class Main {2 static class Node {3 Node[] children = new Node[26];4 boolean isWord;5 }6
7 static Node root = new Node();8
9 static void insert(String word) {10 Node cur = root;11 for (char c : word.toCharArray()) {12 int i = c - 'a';13 if (cur.children[i] == null) cur.children[i] = new Node();14 cur = cur.children[i];15 }16 cur.isWord = true;17 }18
19 // Follow the path for s; null means no word has this prefix20 static Node walk(String s) {21 Node cur = root;22 for (char c : s.toCharArray()) {23 cur = cur.children[c - 'a'];24 if (cur == null) return null;25 }26 return cur;27 }28
29 static boolean search(String word) {30 Node node = walk(word);31 return node != null && node.isWord;32 }33
34 static boolean startsWith(String prefix) {35 return walk(prefix) != null;36 }37
38 public static void main(String[] args) {39 insert("code");40 insert("coder");41 insert("cool");42 System.out.println("search code: " + search("code"));43 System.out.println("search cod: " + search("cod"));44 System.out.println("startsWith cod: " + startsWith("cod"));45 System.out.println("startsWith cat: " + startsWith("cat"));46 }47}Trie (Prefix Tree) code in C++
C++
1#include <iostream>2#include <string>3#include <unordered_map>4
5struct TrieNode {6 std::unordered_map<char, TrieNode*> children;7 bool isEnd = false;8};9
10struct Trie {11 TrieNode* root = new TrieNode();12
13 void insert(const std::string& word) {14 TrieNode* node = root;15 for (char c : word) {16 if (!node->children.count(c)) node->children[c] = new TrieNode();17 node = node->children[c];18 }19 node->isEnd = true;20 }21
22 // Follow the path for s; nullptr if a link is missing23 TrieNode* walk(const std::string& s) const {24 TrieNode* node = root;25 for (char c : s) {26 auto it = node->children.find(c);27 if (it == node->children.end()) return nullptr;28 node = it->second;29 }30 return node;31 }32
33 bool search(const std::string& word) const {34 TrieNode* node = walk(word);35 return node != nullptr && node->isEnd;36 }37
38 bool startsWith(const std::string& prefix) const {39 return walk(prefix) != nullptr;40 }41};42
43int main() {44 Trie trie;45 for (const std::string& word : {"car", "card", "care", "dog"}) {46 trie.insert(word);47 }48 std::cout << std::boolalpha;49 std::cout << "search(card): " << trie.search("card") << "\n";50 std::cout << "search(ca): " << trie.search("ca") << "\n";51 std::cout << "startsWith(ca): " << trie.startsWith("ca") << "\n";52 std::cout << "startsWith(dot): " << trie.startsWith("dot") << "\n";53 return 0;54}Trie (Prefix Tree) code in C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct TrieNode {6 struct TrieNode* children[26];7 bool isEnd;8} TrieNode;9
10TrieNode* newNode(void) {11 return calloc(1, sizeof(TrieNode)); // zeroed links and isEnd12}13
14void insert(TrieNode* root, const char* word) {15 for (; *word; word++) {16 int i = *word - 'a';17 if (root->children[i] == NULL) root->children[i] = newNode();18 root = root->children[i];19 }20 root->isEnd = true;21}22
23// Follow the path for s; NULL if a link is missing24TrieNode* walk(TrieNode* root, const char* s) {25 for (; *s; s++) {26 root = root->children[*s - 'a'];27 if (root == NULL) return NULL;28 }29 return root;30}31
32bool search(TrieNode* root, const char* word) {33 TrieNode* node = walk(root, word);34 return node != NULL && node->isEnd;35}36
37bool startsWith(TrieNode* root, const char* prefix) {38 return walk(root, prefix) != NULL;39}40
41int main(void) {42 TrieNode* root = newNode();43 const char* words[] = {"car", "card", "care", "dog"};44 for (int i = 0; i < 4; i++) insert(root, words[i]);45 printf("search(card): %s\n", search(root, "card") ? "true" : "false");46 printf("search(ca): %s\n", search(root, "ca") ? "true" : "false");47 printf("startsWith(ca): %s\n", startsWith(root, "ca") ? "true" : "false");48 printf("startsWith(dot): %s\n", startsWith(root, "dot") ? "true" : "false");49 return 0;50}Trie FAQ
What is a trie used for?
Tries power prefix-based features: autocomplete and search suggestions, spell-checkers, IP routing tables, and dictionary lookups. Anywhere you need fast "does any stored word start with this prefix?" queries, a trie shines.
What is the time complexity of a trie?
Insert, search, and prefix queries all run in
O(m) time, where m is the length of the word or prefix - independent of how many words are stored. The trade-off is memory: a trie can use a lot of space, though shared prefixes are stored only once.What is the difference between a trie and a hash table?
A hash table offers
O(1) average lookup of whole keys but can't answer prefix queries. A trie is slightly slower per lookup but naturally supports prefix search, ordered traversal, and autocomplete - the reason it's preferred for those use cases.When should I use a trie instead of a binary search tree?
Use a trie when your keys are strings and you need prefix lookups: it runs in
O(m) per operation on the key length, while a balanced BST costs O(m log n) because each comparison scans the string and there are log n of them. A BST is the better choice when keys aren't string-like or when memory overhead matters more than prefix speed.How do you handle the end of a word in a trie?
Each node carries an end-of-word flag that is set only when a full inserted word terminates there. Without it you couldn't tell a stored word from a mere prefix - for example after inserting
card, the node for car exists but should only be reported as a word if car was also inserted.Do tries always save memory by sharing prefixes?
Not always. Sharing helps only when many keys overlap; with long, distinct keys a trie can use far more memory than a hash set, since every character becomes its own node with child pointers. If space is the concern, a compressed radix tree merges single-child chains to cut that overhead.
Related resources
More visualizations
