Trie (Prefix Tree)

Definition

A Trie (pronounced “try”) is a tree-like data structure used efficiently for storing strings. Each node represents a character of a string.

How it Works

Instead of storing a whole word like “Apple” in one node, a Trie breaks it down.

1. The root is empty.
2. The first child is ‘A’.
3. The child of ‘A’ is ‘p’, and so on.
4. Words with common prefixes (like “Car” and “Cat”) share the same initial path (‘C’ $\rightarrow$ ‘a’).

Real-World Analogy:

Think of auto-complete on your phone. When you type “H-E-L”, the phone looks down the path of those specific letters to suggest “Hello” or “Help”. It doesn’t look at words starting with ‘Z’.

Example

Insert: “CAT”, “CAR”

Structure:

Both words share the ‘C-A’ path.

Code Example (Python)

Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = 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]
        self.is_end_of_word = 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 self.is_end_of_word

Complexity Analysis

• Time Complexity: O(L) where L is the length of the word. Searching for a word depends only on the word’s length, not the size of the database!
• Space Complexity: O(N times L) in worst case, but saves space when many words share prefixes.

Use Cases

• Autocomplete/Typeahead: Google search suggestions.
• Spell Checkers: Validating if a word exists in the dictionary.
• IP Routing: Longest prefix matching in internet routers.