Trie: The Prophet

The Story: The Shared Path

Imagine you are walking in a forest of words.

• You want to find “Cat,” “Car,” and “Cart.”
• Do you build three separate roads? No.
• You build one road that starts with ‘C’, then goes to ‘A’.
• At ‘A’, the road forks: one path goes to ‘T’ (Cat), one goes to ‘R’.
• At ‘R’, it forks again: one stops (Car), one goes to ‘T’ (Cart).

This is a Trie (from Retrieval). It merges the common beginnings of words. It allows you to search for all words starting with “Ca” without looking at words starting with “Do”.

Why do we need it?

• Autocomplete: When you type “Alg”, Google instantly suggests “Algorithm”, “Algebra”, “Algiers”. It found the ‘Alg’ node in a Trie and looked at all its children.
• Spell Check: If you type “Appl”, the Trie knows that ‘e’ is a valid next step.
• IP Routing: Routers use Tries to match IP prefixes (192.168.*) to destinations.

How the Algorithm “Thinks”

The algorithm is a Pathfinder.

1. The Node: Every node represents a character.
2. The Edge: The link between nodes.
3. The Flag: A boolean flag is_end_of_word marks where a valid word stops. (e.g., ‘Car’ is a word, but it is also a prefix for ‘Cart’. The node ‘r’ needs a flag).

Complexity:

• Searching for a word of length $L$ takes $O(L)$ time.
• It does not depend on the number of words in the dictionary ($N$). This is why it’s faster than a Hash Map for prefix searches.

Engineering Context: The Memory Cost

Tries are fast, but they eat memory.

• A standard Trie node contains an array of 26 pointers (for ‘a’ to ‘z’). Most of these are usually empty (None).
• Optimization: Engineers use Radix Trees (compressed Tries) where a single node can hold a string like “at” instead of just ‘a’ -> ‘t’.

Implementation (Python)

class TrieNode:
    def __init__(self):
        self.children = {} # Map: char -> TrieNode
        self.is_end = False

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

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

# Usage
trie = Trie()
trie.insert("apple")
print(trie.search("apple"))   # True
print(trie.search("app"))     # False (not a whole word)
print(trie.starts_with("app")) # True

Summary

The Trie teaches us that beginnings matter. By organizing data based on how it starts, we can process input in real-time, predicting the user’s intent before they even finish typing. It reminds us that often, the journey (the prefix) is just as important as the destination (the word).