Data Structures•Last Updated : 25 Oct 2026

~45 min read

Tries (Prefix Trees)

Answer prefix questions in time proportional to the prefix, not the dictionary. Builds a trie from first principles, then covers insert, search versus prefix lookup, autocomplete with sorted results and counts, a comparison with sets and sorted lists, memory trade-offs and using a trie to prune backtracking.

Autocomplete over a hundred thousand words

You are building the search box for a dictionary app. After each keystroke, the app must show words that start with what the user has typed so far. The first idea is a list of 100,000 words and a loop that checks word.startswith(prefix) on every one. That scans every word on every keystroke: about 100,000 checks, even when the prefix is "zy" and only a handful of words match. Multiply by thousands of users typing at once and the server struggles.

Notice what the loop wastes. Words that begin "ca" share their first two letters, yet the scan re-reads those letters for every word. A trie (pronounced "try", from retrieval) stores the shared beginnings once. Finding all words with a given prefix then costs time proportional to the length of the prefix plus the number of results, no matter how large the dictionary is.

Definition: Trie (prefix tree)

A tree in which each edge is labelled with a character and each path from the root spells a prefix. A node marked as a word end represents a stored word. Words with a common prefix share the same path.

Step 1: picture the tree

Insert the words car, card, care, cat and dog. The root is empty. From the root, one branch for c and one for d. Under c there is one a, because every c-word here continues with a. Under that a, the branches split into r and t. Under r, the word car ends (marked with *), and it can also continue to d and e.

Reading a word is walking from the root, following one edge per character. Two words share a node exactly as long as they share a prefix. Notice that car is a word and a prefix of two other words, which is why each node needs its own "a word ends here" flag instead of treating leaves as words.

A trie holding car, card, care, cat, dog

(root)
  |-- c
  |     `-- a
  |          |-- r *          <- "car" ends here, but the path continues
  |          |     |-- d *    <- "card"
  |          |     `-- e *    <- "care"
  |          `-- t *          <- "cat"
  `-- d
        `-- o
             `-- g *         <- "dog"

17 letters stored in 9 nodes below the root: the shared 'c','a','r' are kept once.

* marks a node where a stored word ends. Shared prefixes share nodes.

Step 2: build it with a dictionary per node

Each node holds a dictionary from the next character to the child node, plus a boolean saying whether a word ends here. That is all.

insert(word): walk from the root; for each character, follow the child edge or create it; at the end, set the flag. Cost O(L) for a word of length L.
contains(word): walk the same path; succeed only if the path exists and the final node has the word flag.
starts_with(prefix): walk the path; succeed if the path exists, flag or not.

The distinction between the last two is the most common trie bug: "car" is a prefix of "card" even if "car" itself was never inserted. The example inserts card only and asks all three questions about car. We also keep a count on each node (how many words pass through it) because it will make a later feature cheap.

PythonInsert, contains and starts_with

1class TrieNode:
2    def __init__(self):
3        self.children = {}
4        self.is_word = False
5        self.count = 0          # how many stored words pass through this node
6 
7class Trie:
8    def __init__(self):
9        self.root = TrieNode()
10 
11    def insert(self, word):
12        node = self.root
13        for ch in word:
14            node = node.children.setdefault(ch, TrieNode())
15            node.count += 1
16        node.is_word = True
17 
18    def _walk(self, text):
19        node = self.root
20        for ch in text:
21            node = node.children.get(ch)
22            if node is None:
23                return None
24        return node
25 
26    def contains(self, word):
27        node = self._walk(word)
28        return node is not None and node.is_word
29 
30    def starts_with(self, prefix):
31        return self._walk(prefix) is not None
32 
33    def words_with_prefix(self, prefix, limit=None):
34        node = self._walk(prefix)
35        found = []
36        if node is None:
37            return found
38        stack = [(node, prefix)]
39        while stack:
40            current, text = stack.pop()
41            if current.is_word:
42                found.append(text)
43            for ch in sorted(current.children, reverse=True):
44                stack.append((current.children[ch], text + ch))
45        return found if limit is None else found[:limit]
46 
47trie = Trie()
48for word in ["car", "card", "care", "cat", "dog"]:
49    trie.insert(word)
50 
51print(trie.contains("car"), trie.contains("ca"), trie.contains("cart"))
52print(trie.starts_with("ca"), trie.starts_with("do"), trie.starts_with("cow"))
53 
54only_card = Trie()
55only_card.insert("card")
56print("car in trie of only 'card':", only_card.contains("car"))
57print("'car' is a prefix of 'card':", only_card.starts_with("car"))
58print("words passing through 'ca':", trie._walk("ca").count)

Output

True False False
True True False
car in trie of only 'card': False
'car' is a prefix of 'card': True
words passing through 'ca': 4

Step 3: autocomplete, prefix counts and sorted results

To list every word with a prefix, walk down to the prefix node (O(P) for a prefix of length P), then traverse the whole subtree below it with a depth-first search, collecting each node marked as a word end. The work is proportional to the size of that subtree, which is the number of results (times their lengths), not the size of the dictionary. For "zy" that is tiny even in a 100,000-word dictionary.

Because each node's children are visited in alphabetical order (we sort the keys and push them in reverse onto the stack), the results come out already sorted. Cap the results with limit, since a search box shows maybe eight suggestions, not all thousands.

The count field answers "how many words start with this prefix?" in O(P) without touching the subtree: just read the counter at the prefix node.

PythonSuggestions for a typed prefix

1class TrieNode:
2    def __init__(self):
3        self.children = {}
4        self.is_word = False
5        self.count = 0          # how many stored words pass through this node
6 
7class Trie:
8    def __init__(self):
9        self.root = TrieNode()
10 
11    def insert(self, word):
12        node = self.root
13        for ch in word:
14            node = node.children.setdefault(ch, TrieNode())
15            node.count += 1
16        node.is_word = True
17 
18    def _walk(self, text):
19        node = self.root
20        for ch in text:
21            node = node.children.get(ch)
22            if node is None:
23                return None
24        return node
25 
26    def contains(self, word):
27        node = self._walk(word)
28        return node is not None and node.is_word
29 
30    def starts_with(self, prefix):
31        return self._walk(prefix) is not None
32 
33    def words_with_prefix(self, prefix, limit=None):
34        node = self._walk(prefix)
35        found = []
36        if node is None:
37            return found
38        stack = [(node, prefix)]
39        while stack:
40            current, text = stack.pop()
41            if current.is_word:
42                found.append(text)
43            for ch in sorted(current.children, reverse=True):
44                stack.append((current.children[ch], text + ch))
45        return found if limit is None else found[:limit]
46 
47words = ["apple", "app", "apply", "apt", "banana", "band", "bandana", "ban", "can", "candy", "cane"]
48trie = Trie()
49for w in words:
50    trie.insert(w)
51 
52for typed in ["ap", "ban", "c", "x"]:
53    suggestions = trie.words_with_prefix(typed, limit=4)
54    how_many = trie._walk(typed).count if trie.starts_with(typed) else 0
55    print(repr(typed).ljust(6), "->", suggestions, "| total matches:", how_many)

Output

'ap'   -> ['app', 'apple', 'apply', 'apt'] | total matches: 4
'ban'  -> ['ban', 'banana', 'band', 'bandana'] | total matches: 4
'c'    -> ['can', 'candy', 'cane'] | total matches: 3
'x'    -> [] | total matches: 0

Step 4: how it compares, counting work instead of timing it

Is the trie really cheaper than scanning? Timing depends on the machine, so count character comparisons instead. A linear scan with startswith compares up to P characters against each of N words. A trie checks at most P characters on the path to the prefix, then touches only the matching subtree.

The example builds a synthetic dictionary of every three-letter combination from a small alphabet (so the numbers are exact and reproducible) and counts the steps for a two-letter prefix. Notice the gap grows with the dictionary size, while the trie's cost depends on the number of results.

Alternatives and their trade-offs:

Hash set: O(1) exact lookup, but cannot answer prefix queries without scanning.
Sorted list + binary search: finds the first word with a prefix in O(P log N) and then reads the contiguous block; memory-light and simple, a strong baseline for static dictionaries.
Trie: O(P) prefix lookup, supports inserts and per-prefix counts easily, but uses far more memory per character because every node is an object with a dictionary.

Prefix search options

Structure	Exact lookup	Prefix query	Memory	Good for
Hash set	O(L) average	scan everything, O(N * L)	low	membership only
Sorted array + bisect	O(L log N)	O(P log N) + results	low	static word lists
Trie	O(L)	O(P) + subtree size	high (a node per character)	autocomplete, counting by prefix, many inserts

PythonCounting comparisons: scan versus trie

1class TrieNode:
2    def __init__(self):
3        self.children = {}
4        self.is_word = False
5        self.count = 0          # how many stored words pass through this node
6 
7class Trie:
8    def __init__(self):
9        self.root = TrieNode()
10 
11    def insert(self, word):
12        node = self.root
13        for ch in word:
14            node = node.children.setdefault(ch, TrieNode())
15            node.count += 1
16        node.is_word = True
17 
18    def _walk(self, text):
19        node = self.root
20        for ch in text:
21            node = node.children.get(ch)
22            if node is None:
23                return None
24        return node
25 
26    def contains(self, word):
27        node = self._walk(word)
28        return node is not None and node.is_word
29 
30    def starts_with(self, prefix):
31        return self._walk(prefix) is not None
32 
33    def words_with_prefix(self, prefix, limit=None):
34        node = self._walk(prefix)
35        found = []
36        if node is None:
37            return found
38        stack = [(node, prefix)]
39        while stack:
40            current, text = stack.pop()
41            if current.is_word:
42                found.append(text)
43            for ch in sorted(current.children, reverse=True):
44                stack.append((current.children[ch], text + ch))
45        return found if limit is None else found[:limit]
46 
47from itertools import product
48 
49alphabet = "abcdef"
50words = ["".join(p) for p in product(alphabet, repeat=3)]
51trie = Trie()
52for w in words:
53    trie.insert(w)
54 
55prefix = "ab"
56scan_comparisons = 0
57scan_hits = []
58for w in words:
59    scan_comparisons += len(prefix)
60    if w.startswith(prefix):
61        scan_hits.append(w)
62 
63trie_comparisons = len(prefix)
64trie_hits = trie.words_with_prefix(prefix)
65trie_comparisons += sum(len(w) - len(prefix) for w in trie_hits)
66 
67print("words stored:", len(words))
68print("same results:", scan_hits == trie_hits, len(trie_hits), "matches")
69print("scan character comparisons:", scan_comparisons)
70print("trie character steps:", trie_comparisons)

Output

words stored: 216
same results: True 6 matches
scan character comparisons: 432
trie character steps: 8

Step 5: pruning a search, the trie inside backtracking

A trie is more than autocomplete. Whenever you build candidates one character at a time and need to know if the current prefix can still become a valid word, a trie answers "is there any hope?" in O(1) per step. Word-search puzzles on a letter grid, Boggle solvers and password-pattern checks all use this: extend a path, ask the trie whether the letters so far are a prefix of any word, and abandon the path immediately if not.

Without pruning, a solver explores every path of every length. With pruning, it stops exploring "zq..." the moment it sees that no word begins with zq. The example enumerates paths through a tiny grid and compares the number of paths examined with and without the prefix check.

PythonPrefix pruning shrinks the search

1class TrieNode:
2    def __init__(self):
3        self.children = {}
4        self.is_word = False
5        self.count = 0          # how many stored words pass through this node
6 
7class Trie:
8    def __init__(self):
9        self.root = TrieNode()
10 
11    def insert(self, word):
12        node = self.root
13        for ch in word:
14            node = node.children.setdefault(ch, TrieNode())
15            node.count += 1
16        node.is_word = True
17 
18    def _walk(self, text):
19        node = self.root
20        for ch in text:
21            node = node.children.get(ch)
22            if node is None:
23                return None
24        return node
25 
26    def contains(self, word):
27        node = self._walk(word)
28        return node is not None and node.is_word
29 
30    def starts_with(self, prefix):
31        return self._walk(prefix) is not None
32 
33    def words_with_prefix(self, prefix, limit=None):
34        node = self._walk(prefix)
35        found = []
36        if node is None:
37            return found
38        stack = [(node, prefix)]
39        while stack:
40            current, text = stack.pop()
41            if current.is_word:
42                found.append(text)
43            for ch in sorted(current.children, reverse=True):
44                stack.append((current.children[ch], text + ch))
45        return found if limit is None else found[:limit]
46 
47grid = ["cat", "oad", "ten"]
48dictionary = ["cat", "cot", "cod", "toad", "ten", "neat", "tea", "eat"]
49trie = Trie()
50for w in dictionary:
51    trie.insert(w)
52 
53def solve(prune):
54    found, visited = set(), [0]
55    def dfs(r, c, text, used):
56        visited[0] += 1
57        if prune and not trie.starts_with(text):
58            return
59        if trie.contains(text):
60            found.add(text)
61        if len(text) >= 5:
62            return
63        for dr in (-1, 0, 1):
64            for dc in (-1, 0, 1):
65                nr, nc = r + dr, c + dc
66                if (dr or dc) and 0 <= nr < 3 and 0 <= nc < 3 and (nr, nc) not in used:
67                    dfs(nr, nc, text + grid[nr][nc], used | {(nr, nc)})
68    for r in range(3):
69        for c in range(3):
70            dfs(r, c, grid[r][c], {(r, c)})
71    return sorted(found), visited[0]
72 
73words_a, steps_a = solve(prune=False)
74words_b, steps_b = solve(prune=True)
75print("found:", words_b)
76print("same answer:", words_a == words_b)
77print("paths examined without pruning:", steps_a)
78print("paths examined with trie pruning:", steps_b)

Output

found: ['cat', 'cot', 'eat', 'neat', 'tea', 'ten', 'toad']
same answer: True
paths examined without pruning: 1913
paths examined with trie pruning: 106

Memory, variations and pitfalls

A trie's weakness is memory. In Python every node is an object holding a dictionary; storing a million words can use hundreds of megabytes where a sorted list would use a fraction. Options when that hurts: store children in a fixed-size array indexed by letter (fast, wasteful for sparse nodes), use a compressed trie (radix tree) that merges chains of single-child nodes into one edge labelled with a string, or fall back to a sorted array with binary search.

Variations you will meet: a binary trie over the bits of integers (used for maximum-XOR queries and IP routing tables), a trie that stores a value at each word end (a dictionary with prefix search), and suffix tries for substring queries. Deleting a word means removing nodes that no other word uses, walking back up from the end and decrementing counts; many programs simply never delete.

Edge cases to test: the empty string (the root is a word if you insert it), a word that is a prefix of another, a prefix that is not a word, and uppercase versus lowercase (normalise first).

Best Practices (Do)

✓Keep a separate is_word flag; a word may be a prefix of another
✓Normalise case before inserting and searching
✓Cap the number of suggestions you return
✓Consider a sorted list with bisect for static word lists

Common Pitfalls (Don't)

✕Don't treat leaves as the only words
✕Don't use a trie when you only need exact membership (a set is simpler)
✕Don't forget the memory cost per node
✕Don't confuse contains with starts_with

Check your understanding

Each question targets a place tries go wrong.

Suggested Quiz

Question 1 of 4

A trie stores only the word "card". What do `contains("car")` and `starts_with("car")` return?

Summary

Share prefixes, answer prefix questions fast.

Key Takeaways & Summary

•A trie stores shared prefixes once; each node has child edges and an is-word flag.
•insert, contains and starts_with are O(L); contains also needs the word flag, starts_with does not.
•Autocomplete walks to the prefix node, then collects the subtree; visiting children in sorted order gives sorted results.
•Prefix counts on nodes answer "how many words start with..." in O(P).
•Tries pay for speed with memory; use them for prefix search and for pruning backtracking, not for plain membership.

Quick Syntax & Reference Sheet

Concept / Rule	Syntax / Usage
Node	`children = {} # char -> node is_word = False`
Insert	`for ch in word: node = node.children.setdefault(ch, Node()) node.is_word = True`
Walk a path	`node = node.children.get(ch); stop if None`
contains vs starts_with	`contains: path exists AND node.is_word starts_with: path exists`
Complexity	`insert/search/prefix: O(L); autocomplete: O(P + size of subtree)`

Common Pitfalls & Developer Mistakes

✕ Mistake 1:

Returning True from search whenever the path exists

Why it happens: That answers the prefix question; a stored word "card" would make "car" look like a stored word.

Correction: After walking the path, also check the node's is_word flag.

✕ Mistake 2:

Treating only leaf nodes as words

Why it happens: A word can be a prefix of a longer word (car and card), so it ends at an inner node.

Correction: Mark word ends with a flag on any node.

✕ Mistake 3:

Skipping case normalisation

Why it happens: "Apple" and "apple" take different paths, so searches miss entries.

Correction: Lowercase (and strip) every word and query before using the trie.

Frequently Asked Questions

When should I use a trie instead of a hash set?

Use a hash set when you only ask whether an exact word exists. Use a trie when you ask prefix questions: autocomplete, counting words by prefix, pruning a search or longest-prefix matching.

Is a trie always faster than binary search on a sorted list?

Not always. A sorted list with bisect answers prefix queries in O(P log N) and uses much less memory. A trie wins when the set changes often, when you need per-prefix counts, or when the log N factor matters.

Next: Union-Find (Disjoint Sets) →

Article Tags:#Trie#Prefix Tree#Autocomplete#Strings#Backtracking#Data Structures

Previous TopicTrees & Binary Search Trees

Next TopicUnion-Find (Disjoint Sets)

Was this lesson clear and helpful?

Discussion (0)

Discuss in community

Autocomplete over a hundred thousand words

Step 1: picture the tree

Step 2: build it with a dictionary per node

Step 3: autocomplete, prefix counts and sorted results

Step 4: how it compares, counting work instead of timing it

Prefix search options

Step 5: pruning a search, the trie inside backtracking

Memory, variations and pitfalls

Check your understanding

A trie stores only the word "card". What do `contains("car")` and `starts_with("car")` return?

Summary

Quick Syntax & Reference Sheet

Common Pitfalls & Developer Mistakes

Returning True from search whenever the path exists

Treating only leaf nodes as words

Skipping case normalisation

Frequently Asked Questions

When should I use a trie instead of a hash set?

Is a trie always faster than binary search on a sorted list?

Discussion (0)

Related discussions