Quick answer: A Trie stores strings character by character and shares nodes for common prefixes. It is useful for autocomplete and prefix search, but it uses more structural memory than a dictionary and should be compared with simpler indexes for the actual workload.
A trie is a tree-shaped data structure for storing strings by prefix. Each level represents the next character, so words that share a prefix also share part of the tree.
Tries are useful for autocomplete, prefix search, dictionaries, spell-check helpers, route matching, and word games. They can be faster than scanning a full list when you repeatedly ask questions such as “does this word exist?” or “which words start with this prefix?” Tries organize string prefixes, while Binary Search in Python: Iterative and Recursive finds a value by repeatedly halving an already sorted sequence.
The key idea is shared structure. If you store car, cart, and cat, the trie stores the common ca path once. A list stores each string separately and must compare prefixes repeatedly during search.
Python does not include a built-in trie type, but it is straightforward to implement with dictionaries. For related string work, see how to find a character in a string and how match case in Python can organize branching logic.
Create A Trie Node
A trie node needs a mapping of child characters and a flag that marks the end of a stored word.
from dataclasses import dataclass, field
@dataclass
class TrieNode:
children: dict[str, "TrieNode"] = field(default_factory=dict)
is_word: bool = False
root = TrieNode()
print(root.children)
print(root.is_word)
The root node does not represent a character. It is the starting point for every word inserted into the trie.
Using a dataclass keeps the node definition compact. The default_factory creates a new child dictionary for each node, which prevents nodes from accidentally sharing the same child mapping.
Insert Words
To insert a word, walk character by character. Create missing child nodes along the way, then mark the final node as a complete word.
def insert(root, word):
node = root
for character in word:
node = node.children.setdefault(character, TrieNode())
node.is_word = True
insert(root, "cat")
insert(root, "car")
insert(root, "cart")
The words cat, car, and cart share the first two nodes. That shared prefix is what makes a trie different from storing each word independently.
Insertion time is based on the length of the word, not the number of words already stored. That makes tries attractive when the collection grows and prefix operations remain common.
Search For A Full Word
A full-word search walks the same path as insertion, then checks whether the final node is marked as a word.
def search(root, word):
node = root
for character in word:
if character not in node.children:
return False
node = node.children[character]
return node.is_word
print(search(root, "car"))
print(search(root, "cap"))
This distinction matters because a prefix can exist without being a complete word. After inserting cart, the prefix ca exists, but it may not be stored as a word.
The is_word flag handles that distinction. Without it, the trie could tell that a path exists, but it could not tell whether the path is a complete stored word.
Check Prefixes
Prefix checks stop as soon as the prefix path is found. They do not require the final node to be a complete word.
def starts_with(root, prefix):
node = root
for character in prefix:
if character not in node.children:
return False
node = node.children[character]
return True
print(starts_with(root, "ca"))
print(starts_with(root, "do"))
This is the core operation behind autocomplete. Once the prefix path exists, you can collect every complete word below it.
Prefix checks are also useful before doing heavier work. If no prefix path exists, an autocomplete system can return immediately without scanning every stored word.
Build Autocomplete Suggestions
Autocomplete first walks to the prefix node, then searches downward for stored words.
def autocomplete(root, prefix):
node = root
for character in prefix:
if character not in node.children:
return []
node = node.children[character]
results = []
def collect(current, path):
if current.is_word:
results.append(prefix + path)
for character, child in current.children.items():
collect(child, path + character)
collect(node, "")
return results
print(autocomplete(root, "ca"))
For user-facing search boxes, sort or rank the results before displaying them. The trie finds candidates; ranking decides which suggestions appear first.
Large autocomplete systems often store extra metadata such as frequency or recency near word-ending nodes. That lets the system return useful suggestions instead of only alphabetical matches.
Delete A Word
Deletion should unmark the word and remove nodes that no longer serve any other word.
def delete(root, word):
def remove(node, index):
if index == len(word):
if not node.is_word:
return False
node.is_word = False
return not node.children
character = word[index]
child = node.children.get(character)
if child is None:
return False
should_delete = remove(child, index + 1)
if should_delete:
del node.children[character]
return not node.children and not node.is_word
remove(root, 0)
delete(root, "cart")
print(search(root, "cart"))
Deletion is more careful than insertion because a word can share nodes with other words. Removing cart should not remove car.
The recursive helper returns whether a child node can be removed. A node is safe to remove only when it has no children and is not the end of another word.
When To Use A Trie
Use a trie when prefix queries are a core operation and the data set is searched many times. For one-off lookups, a set or dictionary is simpler. For substring search anywhere inside a string, a trie is usually not the right tool unless you build a specialized variant.
Tries trade memory for prefix speed. Each node stores child mappings, so a large vocabulary can use more memory than a flat list. The payoff is predictable prefix traversal based on the length of the search string.
The reliable pattern is to start with insert, full-word search, and prefix search. Add autocomplete, deletion, ranking, or compression only when your application actually needs those features.
Define A Trie Node
A node typically contains a mapping from characters to child nodes and an end-of-word marker or stored value. Keep the representation explicit so insertion and traversal invariants are easy to test.
Insert And Find Words
Insertion walks or creates one child per character, then marks the final node. Exact lookup must check both the path and the end marker so a stored prefix is not mistaken for a complete word.
Implement Prefix Search
Walk to the node for the prefix, then traverse its descendants to collect completions. Limit result count and depth when the data can be large so autocomplete remains responsive.
Consider Deletion
Deleting a word clears its end marker and removes child nodes only when they are no longer needed by another word. Test shared prefixes and a word that is a prefix of another word.
Compare Dictionaries
A dictionary is usually the simpler and more compact choice for exact keys. A Trie earns its memory and implementation cost when prefix queries, autocomplete, or character-by-character traversal are central.
Test Structural Invariants
Test empty strings according to a documented policy, duplicate insertion, shared prefixes, missing words, prefix-only words, deletion, Unicode characters, and result ordering.
The official Python dictionary documentation is a useful comparison for exact-key lookup. Related Python Pool references include lists and tests.
For related data structures, compare dictionary lookup, list traversal, and invariant tests before choosing a Trie.
Frequently Asked Questions
What is a Trie in Python?
A Trie is a tree-like structure that stores strings character by character so shared prefixes use shared paths.
What is a Trie useful for?
Tries support prefix search, autocomplete, dictionary lookup, and word-oriented routing when their memory tradeoff is acceptable.
How do I mark a complete word?
Store an end-of-word flag or value at the node reached after inserting all characters of the word.
Is a Trie faster than a dictionary for every lookup?
No. A dictionary is often simpler and faster for exact-key lookup; a Trie is valuable when prefix operations are central to the workload.