Trie Data Structure: Definition, How It Works, and Uses

A trie is a tree-like data structure used to store collections of strings where each node represents a character. It allows fast retrieval of words by sharing common prefixes, making it efficient for tasks like autocomplete and spell checking.

How It Works

A trie stores strings by breaking them into characters and placing each character in a node connected like branches of a tree. Starting from the root, each path down the tree spells out a word or prefix. This means words with the same beginning share the same path, saving space and speeding up searches.

Imagine a trie like a filing system where folders represent letters. If you have words like "cat" and "car", they share the folders for 'c' and 'a', then split at the third letter. This structure helps quickly find if a word or prefix exists without checking every word individually.

Example

This example shows how to insert words into a trie and check if a word exists.

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: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

# Usage example
trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("dog")

print(trie.search("car"))  # True
print(trie.search("cap"))  # False

Output

True
False

When to Use

Use a trie when you need fast prefix-based searches or to store many strings with shared beginnings efficiently. Common uses include autocomplete features, spell checkers, IP routing, and word games.

For example, when typing in a search box, a trie can quickly suggest words starting with the letters typed so far. It is also useful when you want to find all words that start with a certain prefix without scanning the entire list.

Key Points

• A trie stores strings by characters in a tree structure.
• It shares common prefixes to save space and speed up searches.
• Supports fast lookup, insertion, and prefix queries.
• Ideal for autocomplete, spell checking, and prefix matching.

Key Takeaways

A trie stores strings as paths of characters sharing common prefixes.

It enables fast search and prefix matching without scanning all words.

Tries are useful for autocomplete, spell checking, and similar tasks.

Each node represents a character and marks if a word ends there.