Trie-Based String Algorithms

Analogy categoryAnalogies

Introduction

A trie (also called a prefix tree) is a tree data structure specialized for storing a set of strings so that common prefixes are shared among nodes. Each node represents a character position, and paths from the root spell out prefixes of the stored strings. Tries support fast insertion, exact-word lookup, and prefix queries (e.g., autocomplete), each in time proportional to the length of the key rather than the number of stored strings.

🏏

Cricket analogy: A trie is like a coaching manual organized by shot technique, where 'cover drive' and 'cover drive on the up' share the same opening branch before diverging; looking up any shot or listing all shots starting with 'cover' takes time proportional to the shot name's length, not the manual's size.

Algorithm/Syntax

python

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end_of_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        node = self._find_node(word)
        return node is not None and node.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        return self._find_node(prefix) is not None

    def _find_node(self, key: str) -> "TrieNode | None":
        node = self.root
        for ch in key:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

Explanation

Insertion walks the string character by character from the root, creating a new child node whenever a required character edge does not already exist, and marks the final node as the end of a word. Search performs the same walk and additionally checks that the final node is flagged as a word end (so 'car' being a prefix of 'card' does not make 'car' a false match unless it was itself inserted). The starts_with (prefix) query only needs to confirm the path exists, without checking the end-of-word flag, which is what powers autocomplete-style features. Because each operation only follows a path whose length equals the key length m, and each step is an O(1) average dictionary lookup, all three operations run in O(m), independent of how many words are stored in the trie.

🏏

Cricket analogy: Inserting 'Kohli' into a name trie walks letter by letter, creating branches only where needed, and flags the final node as a completed entry; searching for 'Koh' alone returns false unless 'Koh' was itself entered as a player name, even though it's a prefix of 'Kohli' — the prefix-check for an autocomplete suggestion list, though, doesn't need that flag.

Example

python

trie = Trie()
for word in ["car", "card", "care", "cart", "dog"]:
    trie.insert(word)

print(trie.search("car"))         # True (inserted exactly)
print(trie.search("ca"))          # False (only a prefix, not inserted as a word)
print(trie.starts_with("ca"))     # True (prefix of car, card, care, cart)
print(trie.starts_with("do"))     # True
print(trie.starts_with("cat"))    # False (no stored word starts with 'cat')

# Structure sketch:
# root -> c -> a -> r (end) -> d (end)
#                        \-> e (end)
#                        \-> t (end)
# root -> d -> o -> g (end)

Complexity

Insertion, exact search, and prefix search each run in O(m) time, where m is the length of the key being processed, regardless of how many words n are stored in the trie. This beats a naive approach of scanning a list of n words with O(n*m) per query. Space complexity is O(ALPHABET_SIZE * N) in the worst case, where N is the total number of trie nodes (bounded by the sum of all inserted string lengths), since shared prefixes reduce redundant storage compared to storing every string independently. Using a dictionary for children (as above) instead of a fixed-size array trades a little constant-factor speed for much better space efficiency with large or sparse alphabets.

🏏

Cricket analogy: Looking up any single player name in a trie of thousands of squad entries takes O(m) time, where m is just the name's length, beating a naive scan of all n names at O(n*m); storing children in a dictionary rather than a fixed 26-letter array trades a little speed for handling names with accented or unusual characters efficiently.

Key Takeaways

A trie stores strings by sharing common prefixes along root-to-node paths, with an is_end_of_word flag marking complete stored words.
Insertion, exact search, and prefix search all run in O(m) time, where m is the key length, independent of the number of stored words.
Prefix queries (starts_with) only need to confirm the path exists, making tries ideal for autocomplete and dictionary lookups.
Space usage grows with the total number of distinct characters/edges needed, but shared prefixes make tries more space-efficient than storing every string independently.

Practice what you learned

1. What is the time complexity of inserting a word of length m into a trie?

2. Why does trie.search('car') need to check is_end_of_word even if the path 'c'->'a'->'r' exists?

3. What distinguishes the starts_with (prefix) query from the search (exact word) query in a trie?

4. What is a major practical use case that motivates the trie data structure?

5. Compared to scanning a list of n words each of length up to m to check if a word exists, what advantage does a trie provide?

Was this page helpful?

Longest Palindromic Substring

Topics covered

#Python#AlgorithmsStudyNotes#Algorithms#TrieBasedStringAlgorithms#Trie#Based#String#Algorithm#StudyNotes#SkillVeris