DSA · Chapter 23 of 40

Tries

A trie (prefix tree) stores strings character by character along paths from the root, so all words sharing a prefix share the same path. Lookup and insert cost O(L) where L is the word length, regardless of how many words are stored.

Tries power autocomplete, spell check and prefix search.

Structure

Each node holds a map from character to child plus a flag marking the end of a word.

Trade-off

Tries are fast for prefix queries but use more memory than a hash set because of the per-character nodes.

Example 1 (python)

class Trie:
    def __init__(self):
        self.root = {}
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node['#'] = True
    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node:
                return False
            node = node[ch]
        return '#' in node

t = Trie()
t.insert('cat')
print(t.search('cat'), t.search('ca'))

Output

True False

The '#' marker distinguishes a full word from a prefix.

Example 2 (python)

def starts_with(trie, prefix):
    node = trie.root
    for ch in prefix:
        if ch not in node:
            return False
        node = node[ch]
    return True
print(starts_with(t, 'ca'))

Output

True

Prefix checks are the main reason to use a trie.

Key points

Insert and search cost O(L), independent of the number of words.
Shared prefixes share nodes.
Mark word ends explicitly.
Tries use more memory than hash sets.

💡 Note: Autocomplete, word search on a board, and prefix counting are the classic trie questions.

Tries

Structure

Trade-off

Key points

📝 Quick Quiz