Tries: Insert and Search

26 min · Intermediate

A trie stores words letter by letter so that words with the same start share the same path. That makes prefix questions, such as which words start with ca, fast. Here you build one with insert, search and a prefix check.

A tree of letters

A trie is a tree where each edge is one character, so every path from the root spells a prefix. A flag on a node marks the end of a stored word. Words with the same start share the same nodes.

Many words start the same way: car, cart, cat. A trie stores each shared start once. Every step down the tree adds one letter. A mark on a node says that a word ends there.

Python

1root = {}2for word in ["car", "cat", "dog"]:3    node = root4    for ch in word:5        node = node.setdefault(ch, {})6    node["end"] = True7print(sorted(root))

A trie holding car, cart, cat and dog. The letters c and a are shared by three words. Gold nodes show where a word ends: r in car, t in cart, t in cat and g in dog.

Example 1 · The nested-dictionary trie

Python

1root = {}2for word in ["car", "cart", "cat"]:3    node = root4    for ch in word:5        node = node.setdefault(ch, {})6    node["end"] = True7print(root)

Output

{'c': {'a': {'r': {'end': True, 't': {'end': True}}, 't': {'end': True}}}}

What this code does

The path c, a, r has an end mark, and it continues to t for cart. Both words share c and a.
This short form is good for contests. An interview usually wants a node class.

Each node is a dictionary from a letter to the next node. setdefault returns the child if it exists, and creates an empty one if not. The key "end" can never clash with a letter, because letters are one character long.

Insert with a node class

Interviews expect a small node class. A node has children, a dictionary from letter to node, and is_end, a flag. To insert, walk down the letters, create missing nodes, and set the flag on the last node.

Python

1class TrieNode:2    def __init__(self):3        self.children = {}4        self.is_end = False5
6def insert(root, word):7    node = root8    for ch in word:9        if ch not in node.children:10            node.children[ch] = TrieNode()11        node = node.children[ch]12    node.is_end = True

Example 2 · A Trie class

Python

1class TrieNode:2    def __init__(self):3        self.children = {}4        self.is_end = 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            if ch not in node.children:15                node.children[ch] = TrieNode()16            node = node.children[ch]17        node.is_end = True18
19    def _walk(self, text):20        node = self.root21        for ch in text:22            node = node.children.get(ch)23            if node is None:24                return None25        return node26
27    def search(self, word):28        node = self._walk(word)29        return node is not None and node.is_end30
31    def starts_with(self, prefix):32        return self._walk(prefix) is not None33
34
35trie = Trie()36for word in ["car", "cart", "cat", "dog"]:37    trie.insert(word)38print(trie.search("car"), trie.search("ca"), trie.search("care"))39print(trie.starts_with("ca"), trie.starts_with("do"), trie.starts_with("x"))

Output

True False False
True True False

What this code does

"ca" is a prefix but not a stored word, so search says False and starts_with says True.
"care" fails at the last letter because no node follows r with an e.

Insert takes one dictionary step per letter, so it costs O(L) time for a word of length L, no matter how many words are stored. New nodes add at most L nodes of space.

Search and starts_with

Search and prefix check share one walk: follow the letters down. If a letter is missing, stop with None. Search then asks if the last node has is_end set. A prefix check only asks if the walk reached a node.

Python

1def walk(root, text):2    node = root3    for ch in text:4        node = node.children.get(ch)5        if node is None:6            return None7    return node8
9def search(root, word):10    node = walk(root, word)11    return node is not None and node.is_end

Example 3 · Search against prefix

Python

1class TrieNode:2    def __init__(self):3        self.children = {}4        self.is_end = 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            if ch not in node.children:15                node.children[ch] = TrieNode()16            node = node.children[ch]17        node.is_end = True18
19    def _walk(self, text):20        node = self.root21        for ch in text:22            node = node.children.get(ch)23            if node is None:24                return None25        return node26
27    def search(self, word):28        node = self._walk(word)29        return node is not None and node.is_end30
31    def starts_with(self, prefix):32        return self._walk(prefix) is not None33
34
35trie = Trie()36trie.insert("net")37for text in ["n", "ne", "net", "nets"]:38    print(text, trie.search(text), trie.starts_with(text))

Output

n False True
ne False True
net True True
nets False False

What this code does

Only "net" is a stored word. The first three are prefixes, and "nets" is neither.
Remember the pair: search needs is_end, starts_with does not.

With car and cart stored, search("ca") is False, since no word ends at a, but the prefix check for "ca" is True. Both cost O(L).

A trie against a list and a set

A set finds an exact word in O(L), since hashing reads every letter. So a trie is not faster for exact search. It wins for prefix questions. A list needs a scan of all N words to answer them.

Python

words = ["car", "cart", "cat", "dog"]print("cat" in set(words))print(any(w.startswith("ca") for w in words))

Example 4 · Shared prefixes save nodes

Python

1class TrieNode:2    def __init__(self):3        self.children = {}4        self.is_end = 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            if ch not in node.children:15                node.children[ch] = TrieNode()16            node = node.children[ch]17        node.is_end = True18
19    def _walk(self, text):20        node = self.root21        for ch in text:22            node = node.children.get(ch)23            if node is None:24                return None25        return node26
27    def search(self, word):28        node = self._walk(word)29        return node is not None and node.is_end30
31    def starts_with(self, prefix):32        return self._walk(prefix) is not None33
34
35def count_nodes(node):36    return 1 + sum(count_nodes(child) for child in node.children.values())37
38
39words = ["car", "cart", "cat", "dog"]40trie = Trie()41for word in words:42    trie.insert(word)43print(sum(len(w) for w in words), count_nodes(trie.root) - 1)

Output

13 8

What this code does

There are 13 letters in the four words, but only 8 letter nodes. c and a are stored once, and car is reused inside cart.
count_nodes calls itself on every child, which is a depth-first walk.

Example 5 · A trie and a plain scan agree

Python

1class TrieNode:2    def __init__(self):3        self.children = {}4        self.is_end = 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            if ch not in node.children:15                node.children[ch] = TrieNode()16            node = node.children[ch]17        node.is_end = True18
19    def _walk(self, text):20        node = self.root21        for ch in text:22            node = node.children.get(ch)23            if node is None:24                return None25        return node26
27    def search(self, word):28        node = self._walk(word)29        return node is not None and node.is_end30
31    def starts_with(self, prefix):32        return self._walk(prefix) is not None33
34
35import random36
37random.seed(5)38words = ["".join(random.choice("abc") for _ in range(random.randint(1, 5))) for _ in range(300)]39trie = Trie()40for word in words:41    trie.insert(word)42ok = True43for prefix in ["a", "ab", "bca", "cc", "abcab", "z"]:44    by_scan = any(w.startswith(prefix) for w in words)45    ok = ok and by_scan == trie.starts_with(prefix)46print(ok)

Output

True

What this code does

The simple scan is the checker. It is slow but obviously right.
On 300 random words both methods give the same answer for every prefix.

The scan with startswith costs O(N times L). A trie answers the same prefix question in O(L), and can also list or count every word under that prefix. The price is more memory, since each letter is a node.

Next step

Check your understanding

10 quick questions

A tree of letters

A trie is a tree where each edge is one character, so every path from the root spells a prefix. A flag on a node marks the end of a stored word. Words with the same start share the same nodes.

Many words start the same way: car, cart, cat. A trie stores each shared start once. Every step down the tree adds one letter. A mark on a node says that a word ends there.

1class TrieNode:2 def __init__(self):3 self.children = {}4 self.is_end = False5 6def insert(root, word):7 node = root8 for ch in word:9 if ch not in node.children:10 node.children[ch] = TrieNode()11 node = node.children[ch]12 node.is_end = True

1class TrieNode:2 def __init__(self):3 self.children = {}4 self.is_end = 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 if ch not in node.children:15 node.children[ch] = TrieNode()16 node = node.children[ch]17 node.is_end = True18 19 def _walk(self, text):20 node = self.root21 for ch in text:22 node = node.children.get(ch)23 if node is None:24 return None25 return node26 27 def search(self, word):28 node = self._walk(word)29 return node is not None and node.is_end30 31 def starts_with(self, prefix):32 return self._walk(prefix) is not None33 34 35trie = Trie()36for word in ["car", "cart", "cat", "dog"]:37 trie.insert(word)38print(trie.search("car"), trie.search("ca"), trie.search("care"))39print(trie.starts_with("ca"), trie.starts_with("do"), trie.starts_with("x"))

1def walk(root, text):2 node = root3 for ch in text:4 node = node.children.get(ch)5 if node is None:6 return None7 return node8 9def search(root, word):10 node = walk(root, word)11 return node is not None and node.is_end

1class TrieNode:2 def __init__(self):3 self.children = {}4 self.is_end = 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 if ch not in node.children:15 node.children[ch] = TrieNode()16 node = node.children[ch]17 node.is_end = True18 19 def _walk(self, text):20 node = self.root21 for ch in text:22 node = node.children.get(ch)23 if node is None:24 return None25 return node26 27 def search(self, word):28 node = self._walk(word)29 return node is not None and node.is_end30 31 def starts_with(self, prefix):32 return self._walk(prefix) is not None33 34 35trie = Trie()36trie.insert("net")37for text in ["n", "ne", "net", "nets"]:38 print(text, trie.search(text), trie.starts_with(text))

1class TrieNode:2 def __init__(self):3 self.children = {}4 self.is_end = 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 if ch not in node.children:15 node.children[ch] = TrieNode()16 node = node.children[ch]17 node.is_end = True18 19 def _walk(self, text):20 node = self.root21 for ch in text:22 node = node.children.get(ch)23 if node is None:24 return None25 return node26 27 def search(self, word):28 node = self._walk(word)29 return node is not None and node.is_end30 31 def starts_with(self, prefix):32 return self._walk(prefix) is not None33 34 35def count_nodes(node):36 return 1 + sum(count_nodes(child) for child in node.children.values())37 38 39words = ["car", "cart", "cat", "dog"]40trie = Trie()41for word in words:42 trie.insert(word)43print(sum(len(w) for w in words), count_nodes(trie.root) - 1)

1class TrieNode:2 def __init__(self):3 self.children = {}4 self.is_end = 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 if ch not in node.children:15 node.children[ch] = TrieNode()16 node = node.children[ch]17 node.is_end = True18 19 def _walk(self, text):20 node = self.root21 for ch in text:22 node = node.children.get(ch)23 if node is None:24 return None25 return node26 27 def search(self, word):28 node = self._walk(word)29 return node is not None and node.is_end30 31 def starts_with(self, prefix):32 return self._walk(prefix) is not None33 34 35import random36 37random.seed(5)38words = ["".join(random.choice("abc") for _ in range(random.randint(1, 5))) for _ in range(300)]39trie = Trie()40for word in words:41 trie.insert(word)42ok = True43for prefix in ["a", "ab", "bca", "cc", "abcab", "z"]:44 by_scan = any(w.startswith(prefix) for w in words)45 ok = ok and by_scan == trie.starts_with(prefix)46print(ok)