TreesData structureaka prefix tree, digital tree, radix tree (compressed)

Trie

A tree keyed by characters where each root-to-node path spells a prefix, giving O(L) insert, lookup and prefix search independent of how many words are stored.

▶ Visualize Pattern: Depth-First Search Practice (3)

Progress

Definition

A trie stores a set of strings as a tree in which each edge is labeled with one character and each node represents the prefix spelled by the path from the root. Words that share a prefix share the path for that prefix. A boolean isEnd flag marks nodes where a stored word terminates.

Every operation walks one character at a time, so insert, exact search and startsWith all cost O(L) for a word of length L — independent of the number of stored words. That is what makes tries the tool for autocomplete, spell checking, IP routing (binary trie on address bits), and problems asking about prefixes or maximum XOR pairs.

The price is memory: a node with a 26-slot child array costs 26 pointers even when only one is used. Hash-map children, or compressing single-child chains into a radix tree, reduce this considerably.

prefixstringsautocompleteO(L)dictionary

Intuition

A mental model before the formal terms.

Picture a phone tree: "press 1 for sales, 2 for support…". Each digit you press narrows you further down the menu, and callers who press the same first digits share the same path. A trie is that menu for characters: to look up "cat" you press c, then a, then t, and check whether that spot is marked as a complete word.

Finding all words with prefix "ca" is walking to the "ca" node and then listing everything beneath it. No scanning of unrelated words ever happens.

How it works

Insert(word): start at the root; for each character, create the child if missing and move into it; mark the final node isEnd = true.
Search(word): walk the characters; return false on any missing child; at the end return the node's isEnd.
startsWith(prefix): same walk, but return true as soon as the walk completes, regardless of isEnd.
Delete(word): walk down, clear isEnd, then on the way back up remove child nodes that have no children and are not word ends.
Optional augmentations: a count per node for "how many words have this prefix", or storing the full word at end nodes for Word Search (Grid DFS)-style board searches.

Why it works

Each node corresponds to exactly one prefix, so the tree is a deterministic automaton: the walk for a word either exists or fails at the first character that has never been seen after that prefix. Membership is thus decided by the walk and one flag.

The cost of a walk is the word length; the size of the alphabet only affects the per-step child lookup (O(1) with an array or hash map).

Operations

Operation	Description	Cost
insert(word)	Create missing nodes along the path and mark the end.	O(L)
search(word)	Walk the path and check the end flag.	O(L)
startsWith(prefix)	Walk the path; succeed if it exists.	O(L)
delete(word)	Unmark the end and prune childless, non-terminal nodes on the way up.	O(L)
wordsWithPrefix(prefix)	Walk to the prefix node, then DFS its subtree.	O(L + output)
countPrefix(prefix)	With per-node counters, read the count at the prefix node.	O(L)

Recognition

How to tell a problem wants this.

The problem mentions prefix, autocomplete, starts with, dictionary of words, or "words on a board".
Many queries against a fixed set of strings where per-query O(L) matters.
Maximum XOR of two numbers — a binary trie over 31 bits.
Keys are strings and you need lexicographic ordering of results (DFS over children in order).

“connected groups” → Depth-First Search “all combinations” → Backtracking “prefix” → Trie

Interactive demo

Play, step, change the input. ← → and space work too.

Commands — insert W, search W, startsWith W — lowercase words, comma separated

1/43Empty trie: only the root. Each edge holds one character, and a node with the "end" badge terminates a stored word.

Matched prefixCurrent nodeNew nodeMatch / word end

PseudocodeLearn Trie →

1node = root
2for ch in word:
3  if ch not in node.children: (insert) create child / (search) return false
4  node = node.children[ch]
5insert: node.end = true
6search: return node.end
7startsWith: return true

Variables

words0

Complexity

access —

search O(L)

insert O(L)

delete O(L)

Speed

Pseudocode

1insert(word):
2  node = root
3  for ch in word:
4    if ch not in node.children: node.children[ch] = new Node()
5    node = node.children[ch]
6  node.isEnd = true
7search(word): node = walk(word); return node != null and node.isEnd
8startsWith(prefix): return walk(prefix) != null

Implementation

1from typing import Optional
2 
3 
41 · Node with dict children and end flag
5class TrieNode:
6    __slots__ = ("children", "is_end")
7 
8    def __init__(self) -> None:
9        self.children: dict[str, "TrieNode"] = {}
10        self.is_end = False
11 
12 
13class Trie:
14    def __init__(self) -> None:
15        self.root = TrieNode()
16 
172 · Insert by walking / creating one node per character
18    def insert(self, word: str) -> None:
19        cur = self.root
20        for ch in word:
21            cur = cur.children.setdefault(ch, TrieNode())
22        cur.is_end = True
23 
243 · Search (exact word) and startsWith (prefix)
25    def _find(self, s: str) -> Optional[TrieNode]:
26        cur = self.root
27        for ch in s:
28            nxt = cur.children.get(ch)
29            if nxt is None:
30                return None
31            cur = nxt
32        return cur
33 
34    def search(self, word: str) -> bool:
35        n = self._find(word)
36        return n is not None and n.is_end
37 
38    def starts_with(self, prefix: str) -> bool:
39        return self._find(prefix) is not None
40 
414 · Delete with pruning of now-empty nodes
42    def remove(self, word: str) -> bool:
43        def go(n: TrieNode, depth: int) -> bool:
44            if depth == len(word):
45                if not n.is_end:
46                    return False
47                n.is_end = False
48                return True
49            ch = word[depth]
50            child = n.children.get(ch)
51            if child is None:
52                return False
53            existed = go(child, depth + 1)
54            if existed and not child.is_end and not child.children:
55                del n.children[ch]
56            return existed
57 
58        return go(self.root, 0)

Walkthrough

TrieNode uses __slots__ to shrink per-node memory, and a dict[str, TrieNode] for children.
insert uses dict.setdefault(ch, TrieNode()) to get-or-create in one expression.
_find walks with dict.get, returning None on a missing character; search and starts_with build on it.
remove recurses, clears is_end, and deletes the child key when not child.children and not an end.

Complexity (this implementation)

time O(L) per operation · space O(total characters)

setdefault constructs a throw-away TrieNode() even when the key exists; use if ch not in cur.children for hot loops.

Language notes

__slots__ cuts memory per node roughly in half, which matters for tries with millions of nodes.
A nested-dict trie ({"a": {"p": {"$": True}}}) is a common quick-and-dirty alternative with no class at all.
Python strings iterate by code point, so Unicode works without extra care.

Common mistakes in this language

Using defaultdict(TrieNode) and accidentally creating nodes during search.
Checking if child.children == {} instead of not child.children (works, but non-idiomatic).
Forgetting is_end and treating every reachable node as a word.

Language differences that matter here

Children storage: C++ uses a fixed std::array of 26 owned pointers (fast, memory-heavy); JS/TS use Map; Python uses dict — the dynamic versions handle any alphabet.
Unicode: Python and JS for...of iterate code points; C++ char iteration is byte-wise, so UTF-8 multi-byte characters break the ch - 'a' indexing.
Memory management: C++ unique_ptr::reset() frees a pruned subtree immediately; the others rely on GC after delete/del.

Complexity

Operation	Average	Worst	Note
Access	—	—	No positional access.
Search	O(L)	O(L)	L = key length.
Insert	O(L)	O(L)
Delete	O(L)	O(L)
Update	O(L)	O(L)	Delete + insert.
Prefix lookup	O(L)	O(L)
Enumerate prefix	O(L + k)	O(L + k)	k = total length of matching words.
Space	O(N · L · σ)		N words, length L, alphabet σ with array children; O(total characters) with hash-map children.

Advantages & disadvantages

Advantages

Lookup time depends only on key length, not on the number of keys.
Prefix queries and lexicographic enumeration come for free.
No hash collisions and no comparisons of whole strings.

Disadvantages

Memory heavy: up to alphabet-size pointers per node; a million short words can use hundreds of MB with fixed arrays.
Slower than a Hash Set for exact lookups of long, non-overlapping keys in practice due to pointer chasing.
Only works when keys decompose into a fixed alphabet.

Use cases

Autocomplete and search-as-you-type suggestions.
Spell checkers and dictionaries; word games (Boggle, Scrabble solvers).
IP routing tables (longest-prefix match) using a binary trie.
Maximum XOR pair queries with a bitwise trie; Aho–Corasick builds on a trie for multi-pattern matching.

Use it when

Prefix queries: autocomplete, "does any word start with…", longest common prefix.
Many membership queries on a fixed dictionary where O(L) per query is required.
Bitwise problems (max XOR) where numbers are keys over the alphabet {0, 1}.
Searching a grid for many words at once (Word Search (Grid DFS) with a dictionary).

Avoid it when

Only exact membership is needed — a Hash Set is simpler and usually faster.
Memory is tight and the key set is huge with little prefix sharing.
Keys are not sequences over a small alphabet (arbitrary objects, floats).

Alternatives

Hash Set Hash Map Suffix Array Aho–Corasick Binary Search Tree

Compare: Trie vs Hash Map

Common mistakes

Returning true from search when the walk succeeds without checking isEnd (that is startsWith).
Forgetting to create the child before moving into it during insert.
Deleting by clearing isEnd only and never pruning — correct but leaks memory; pruning a node that still has descendants is the opposite bug.
Using a 26-array with uppercase or non-letter input, indexing out of bounds.

Interview patterns

Implement Trie (insert/search/startsWith) — the canonical warm-up.
Word Search II: put the dictionary in a trie and DFS the board pruning on missing children.
Design add-and-search with . wildcards via DFS branching over all children.
Maximum XOR of two numbers using a bit trie, greedily preferring the opposite bit.
Replace words / longest word built one character at a time via prefix flags.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
Stack versus queueBeginner
Recursion versus iterationIntermediate
When space complexity mattersIntermediate

Mock interviews

Course ScheduleIntermediate
Number of IslandsIntermediate
Word SearchAdvanced

Interview problems

Implement Trie (Prefix Tree)medium Word Search IIhard Word Breakmedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related