Tries

A trie (from retrieval, said either "try" or "tree") stores a set of strings by spelling each one out as a path from the root, one character per edge, with every string that shares a prefix sharing that prefix's path. It trades the O(1)-average lookup of a hash set for something a hash set cannot do at all: answer "what starts with this prefix" without touching every string you have stored.

1. A tree whose edges are characters

Insert cat, car, card, and dog. cat and car share the path c -> a and only fork at the third letter; card continues past car; dog shares nothing with the others and gets its own branch from the root.

The key lives on the path, not in the node.

A hash set node "is" the string it holds; a trie node is just a fork in the road. Reading cat back out means walking root -> c -> a -> t and concatenating the edge labels you crossed - the node at the end of that walk does not know its own name.

2. Building and searching

The fastest correct implementation needs no custom class at all: a defaultdict whose values are themselves defaultdicts builds the entire branching structure for you, one line per insert.

from collections import defaultdict

 

def make_trie():

return defaultdict(make_trie) # a node is a dict of char -> node

 

root = make_trie()

END = '$' # a sentinel key marks "word ends here"

 

def insert(root, word):

node = root

for ch in word:

node = node[ch] # defaultdict creates the branch

node[END] = True

 

def search(root, word):

node = root

for ch in word:

if ch not in node:

return False

node = node[ch]

return END in node

The explicit version makes the same structure visible as a class, which is worth seeing once because most interview solutions are written this way:

class TrieNode:

def __init__(self):

self.children = {} # char -> TrieNode

self.is_word = False

 

class Trie:

def __init__(self):

self.root = TrieNode()

 

def insert(self, word):

node = self.root

for ch in word:

if ch not in node.children:

node.children[ch] = TrieNode()

node = node.children[ch]

node.is_word = True

 

def search(self, word):

node = self._walk(word)

return node is not None and node.is_word

 

def starts_with(self, prefix):

return self._walk(prefix) is not None

 

def _walk(self, s):

node = self.root

for ch in s:

if ch not in node.children:

return None

node = node.children[ch]

return node

search and starts_with differ by exactly one check: starts_with only needs the walk to succeed, search additionally needs the node it lands on to be a real word's end, not just a fork other words pass through.

3. The end-of-word flag

Every node in the diagram above sits on some path, but only four of them are the end of a stored word. Without a flag marking that, the trie cannot tell "this string was inserted" apart from "this string is a prefix of something that was inserted" - and those are different questions with different answers.

⚠

"ca" being walkable does not make it a stored word

A node with children is not automatically a word, and search must check the flag, not just the walk. If insert never sets is_word for ca, then "ca" in words must return False even though every character of ca has a node - _walk("ca") succeeds and returns a real node, but that node's is_word is False. This is exactly why search is two checks (_walk succeeds and is_word) while starts_with is only one. Confusing them makes every prefix of every inserted word look like it was inserted too.

4. What a trie costs

Every trie operation - insert, search, prefix check - costs O(L), where L is the length of the string involved. Not O(log n), not O(n): the number of other strings already stored never enters the cost at all, because each step only ever looks at the current node's children dict for the next character.

A trie's cost is a property of the query, not the collection.

Searching a trie holding three words or three million costs the same O(L) for a word of length L, because the walk never has a reason to look sideways at any sibling branch. A hash set matches that for exact lookup, but a trie is the only structure of the two that can also answer prefix questions in O(L), without a scan over anything.

Operation	Hash set of strings	Trie
Insert one string	O(L) amortized (hash the whole string)	O(L)
Exact search	O(L) amortized	O(L)
"Does any stored word start with this prefix?"	O(n * L) - check every string	O(L) - one walk
List all words with a given prefix	O(n * L) scan	O(L) to find the node, then one DFS over just that subtree
Memory	one copy of each string	shared prefixes stored once, but each node has real overhead (a dict, an object)

That memory line is the honest trade-off: a trie of many short, low-overlap strings can use more memory than a hash set of the same strings, because every branch point is its own node with its own dictionary, and Python object overhead is not free. Tries win when strings share prefixes heavily and when prefix queries are actually asked - not automatically, and not for free.

5. The problems a trie makes easy

Prefix search / autocomplete. Walk the prefix to find its node in O(L), then DFS the subtree under that node to collect every completion - the trie does the filtering for you; nothing outside that subtree is ever visited.

def words_with_prefix(root, prefix):

node = root

for ch in prefix:

if ch not in node:

return []

node = node[ch]

 

out = []

def collect(n, path):

if END in n:

out.append(prefix + path)

for ch, child in n.items():

if ch != END:

collect(child, path + ch)

collect(node, '')

return out

Word search on a board (LeetCode 212). Given a grid of letters and a list of target words, a naive DFS-per-word re-scans the whole board once per word. Inserting all target words into one trie first lets a single DFS over the board prune itself: at each cell, only step to a neighbour whose letter is an actual child of the current trie node. The instant a partial path has no matching trie node, that entire branch of the board search dies immediately, rather than continuing to build a string nobody is looking for.

⚠

Not pruning the trie node makes the board DFS no faster than brute force

The speedup only exists if the board DFS carries the current trie node along and stops the moment letter not in node.children. A solution that still builds the full candidate string at every cell and checks it against the trie only at the end has paid for the trie's memory without collecting its actual benefit - the pruning has to happen during the walk, not after it. The other common version of this bug is not removing a found word's is_word flag (or a found marker) once reported, which lets the same word be reported twice if the board contains it via two different paths.

Maximum XOR of two numbers (a binary trie over bits). Fix a bit width and insert every number as a path of 0/1 edges, most significant bit first. To maximize x XOR y for a query x, walk the trie greedily: at each level, XOR is maximized by disagreeing on that bit, so try to step to the child labelled with x's current bit flipped - and only fall back to the matching bit if that branch does not exist.

A 2-bit binary trie holding 01, 10, and 11 (00 was never inserted, dimmed). Querying 01 for its max XOR partner: flip the top bit (want 1, it exists), then flip the next bit (want 0, it exists) - landing on 10. 01 XOR 10 = 3, the true max among these three numbers.

BITS = 2 # widen to e.g. 31 for real integers

 

def insert_bits(root, x):

node = root

for i in range(BITS - 1, -1, -1):

b = (x >> i) & 1

node = node.setdefault(b, {})

 

def max_xor_partner(root, x):

node = root

best = 0

for i in range(BITS - 1, -1, -1):

b = (x >> i) & 1

want = 1 - b # the bit that maximizes this position

if want in node:

best |= (1 << i)

node = node[want]

else:

node = node[b]

return best

tip

Always fix the bit width up front and walk most-significant-bit first. Both numbers being compared need to branch at the same positions for "flip the bit" to mean the same thing on both sides. BITS = 31 covers ordinary 32-bit signed integers with room for the sign bit; get this wrong and two numbers that should share a long common prefix instead diverge at the wrong level.

6. Variants worth knowing

Chains of single-child nodes collapse into one edge. The trie above becomes three edges instead of eight - 'ca' labels one edge, then a fork for 't' vs 'rd'.

Variant	What changes	When it earns its keep
Compressed / radix trie	A chain of single-child nodes collapses into one edge labelled with a whole substring, not one character.	Long shared prefixes with few branch points - IP routing tables, file-path tries, anywhere the alphabet-per-node overhead of a plain trie is the bottleneck.
Suffix trie	Insert every suffix of one string as its own trie path.	Any-substring queries ("does X contain Y") in O(length of Y), at O(n^2) space for a length-n string - the naive suffix trie is rarely built as-is.
Suffix automaton / suffix tree	The same substring queries as a suffix trie, built to use only O(n) states by merging equivalent suffixes.	The production-grade version of the line above - real substring-indexing workloads use one of these, not a raw suffix trie.
Sorted list + bisect	No tree at all: keep the strings sorted and binary-search for a prefix's range.	The input is static (no inserts after the first build). bisect_left/bisect_right on the prefix find the same range a trie would, in O(log n) comparisons of O(L) each, with far less memory than any trie.

note

A static set of strings rarely needs a trie at all. If nothing is ever inserted after the initial build, sort the list once and use bisect.bisect_left/bisect_right against prefix and prefix + '￿' to carve out the matching range - no nodes, no dictionaries, no per-character object overhead. Reach for an actual trie when strings are inserted incrementally, or when the branching structure itself is the thing being exploited, as in the XOR trie above.

Where to go next

• Heaps & Priority Queues - the other tree on this shelf that is rarely drawn with TreeNode pointers in real code.
• Range Query Trees - segment trees and Fenwick trees, the other family of trees built for one specific query rather than general storage.
• Trees in the Wild - where tries show up as autocomplete, IP routing, and spell-check, outside of interview problems.
• Balanced Trees - the general-purpose ordered-string alternative to a trie, with O(log n) operations instead of O(L) but no prefix-query shortcut.